Jump to content

Addition, but not for numbers!


Piasa

Recommended Posts

This is a fun and short post on how addition/subtraction can be used for logic and not just numbers.

The example I use is "x & -x".  This expression takes a vector, finds the rightmost 1 and sets all left bits to 0.  The right bits are already 0.  If the input is 0, the expression returns an all 0 vector.  Thus the expression either gives a 1-hot vector of the rightmost 1, or gives 0 if there is no bit set to 1.

There are a lot of interesting expressions.  But some are imperfect for use.  For example "x | (x-1)" will find the rightmost 1 and set all bits to the right to 1.  But if the input is 0 and a 1 isn't found the result is all 1's.  

I've provided a short table on some of the expressions and what they do and what they do in the all 0 or all 1 case.  I think it is accurate but I haven't fully checked all of them. 

These are rarely used, but are useful for inductive logic.  I've found this to be a useful interview question as it allows someone to show they can take an expression like "x & (x-1)" and describe what it does from a practical perspective.  It also allows them to describe why the implementation might be good or bad vs other coding choices.  The use of the carry chain means the logic will hotspot more than versions that don't use the carry chain.  But if the logic is very local this isn't an issue.

+-----------------------------------------+------------+----------+
| Task                                    | expression | not found|
+-----------------------------------------+------------+----------+
| find the rightmost 1:                   |            |          |   
|   leave unchanged (1)                   |            |          |   
|     leave bits on left unchanged        |            |          |   
|       leave bits on right unchanged (0) | x          |  0 ->  0 | 
|       set bits on right to 1:           | x | (x-1)  |  0 -> -1 |
|     set bits on left to 0:              |            |          |   
|       leave bits on right unchanged (0) | x & -x     |  0 ->  0 | 
|       set bits on right to 1:           | x ^ (x-1)  |  0 -> -1 |
|     set bits on left to 1:              |            |          |   
|       leave bits on right unchanged (0) | x | -x     |  0 -> -1 |
|       set bits on right to 1:           | -1         |  0 -> -1 |
+-----------------------------------------+------------+----------+
| find the rightmost 1:                   |            |          |   
|   clear (0)                             |            |          |   
|     leave bits on left unchanged        |            |          |   
|       leave bits on right unchanged (0) | x & (x-1)  |  0 ->  0 | 
|       set bits on right to 1:           | x-1        |  0 -> -1 |
|     set bits on left to 0:              |            |          |   
|       leave bits on right unchanged (0) | 0          |  0 ->  0 | 
|       set bits on right to 1:           | ~x & (x-1) |  0 -> -1 |
|     set bits on left to 1:              |            |          |   
|       leave bits on right unchanged (0) | x ^ -x     |  0 -> -1 |
|       set bits on right to 1:           | ~x | (x-1) |  0 -> -1 |
+-----------------------------------------+------------+----------+
| Task                                    | expression | not found|
+-----------------------------------------+------------+----------+
| find the rightmost 0:                   |            |          |   
|   leave unchanged (0)                   |            |          |   
|     leave bits on left unchanged        |            |          |   
|       leave bits on right unchanged (1) | x          | -1 -> -1 |
|       set bits on right to 0:           | x & (x+1)  | -1 ->  0 | 
|     set bits on left to 0:              |            |          |   
|       leave bits on right unchanged (1) | x & (~x-1) | -1 -> -1 |
|       set bits on right to 0:           | 0          | -1 ->  0 | 
|     set bits on left to 1:              |            |          |   
|       leave bits on right unchanged (1) | x | (~x-1) | -1 -> -1 |
|       set bits on right to 0:           | ~x ^ (x+1) | -1 ->  0 | 
+-----------------------------------------+------------+----------+
| find the rightmost 0:                   |            |          |   
|   set (1)                               |            |          |   
|     leave bits on left unchanged        |            |          |   
|       leave bits on right unchanged (1) | x | (x+1)  | -1 -> -1 |
|       set bits on right to 0:           | x+1        | -1 ->  0 | 
|     set bits on left to 0:              |            |          |   
|       leave bits on right unchanged (1) | x ^ (x+1)  | -1 -> -1 |
|       set bits on right to 0:           | ~x & (x+1) | -1 ->  0 | 
|     set bits on left to 1:              |            |          |   
|       leave bits on right unchanged (1) | -1         | -1 -> -1 |
|       set bits on right to 0:           | ~x | (x+1) | -1 ->  0 | 
+-----------------------------------------+------------+----------+

For cases where the all 0 or all 1 case results in an undesired value, you might need to either do a compare and mux, or extend the vector by 1 bit and use the msb for a mux.

Hopefully some of these expressions are useful or educational.  

Link to comment
Share on other sites

@Piasa,

Nice!

7 hours ago, Piasa said:

I've provided a short table on some of the expressions and what they do and what they do in the all 0 or all 1 case.  I think it is accurate but I haven't fully checked all of them. 

Well now, who's going to post a short Project Vault demo for verification?

Link to comment
Share on other sites

@Piasa, I'm not one to complain about interesting ideas provided for free.... but. What would be more fun and useful would be finding the leading 1 in a std_logic_vector. I know of a lot of things to do with that.

I realize that this is a philosophical issue but I've found that asking questions that try to expose an interviewee's cleverness or ability to solve problems in an interview setting don't necessarily get you the best new employee. The job interview is probably the least successful venture that companies engage in.

Link to comment
Share on other sites

  • 2 weeks later...

For FPGAs, take the input and make a bit-reversed version.  This can be done with a function in VHDL

-- reverses a std_logic_vector and returns a value with the same range as input.
function reverse(x : std_logic_vector) return std_logic_vector is
  variable xnml   : std_logic_vector(x'length-1 downto 0) := x;
  variable rev    : std_logic_vector(0 to x'length-1);
  variable result : std_logic_vector(x'range);
begin
  for i in xnml'range loop
    rev(i) := xnml(i);
  end loop;
  result := rev;
  return result;
end function;

-- find leftmost 1 and return a 1 hot version
function leftmost(x : std_logic_vector) return std_logic_vector is
  variable xnml : std_logic_vector(x'length-1 downto 0) := x;
  variable rev  : signed(x'length-1 downto 0);
begin
  rev := signed(reverse(xnml));
  return reverse(std_logic_vector( rev & -rev));
end function; 

This requires the unary "-" function, which can be imported from std_logic_signed, or by having a signed vector.

If you want the index of the leftmost 1, that would be a priority encoder.

Link to comment
Share on other sites

Archived

This topic is now archived and is closed to further replies.

×
×
  • Create New...