17

Let i be a signed integer type. Consider

i += (i&-i);
i -= (i&-i);

where initially i>0.

  1. What do these do? Is there an equivalent code using arithmetic only?
  2. Is this dependent on a specific bit representation of negative integers?

Source: setter's code of an online coding puzzle (w/o any explanation/comments).

Walter
  • 44,150
  • 20
  • 113
  • 196
  • 4
    Interesting aside, `i & -i` forms a fractal pattern for contiguous values of `i`, for example: `0 1 2 1 4 1 2 1 8 1 4 1 2 1 16 1 2 1 4 ...` – alter_igel Jul 19 '18 at 06:21
  • 3
    Hope [this](https://www.hackerearth.com/practice/data-structures/advanced-data-structures/fenwick-binary-indexed-trees/tutorial/) article will help you. Nicely explained there. – BishalG Jul 19 '18 at 06:24
  • @BishalGautam This link doesn't work properly (if you're not logged into hackerrank I presume). – Walter Jul 19 '18 at 06:28
  • 4
    @Walter, it is working fine for me even without login in. The article is "Fenwick (Binary Indexed) Trees tutorial in HackerEarth". This can also be accessed through Code Monk App (https://play.google.com/store/apps/details?id=com.hackerearth.codemonk&hl=en) . – BishalG Jul 19 '18 at 06:39
  • @BishalGautam This must be because you have an account. No chance here. – Walter Jul 19 '18 at 06:51
  • 3
    @Walter I don't have an account and i can view it. – Fantastic Mr Fox Jul 19 '18 at 06:59
  • 2
    @Walter It's accessible publically. Something blocks on your side. E.g. disabled cookies :P – Swift - Friday Pie Jul 19 '18 at 07:05
  • @Walter, I don't know why you are facing problem. But, seems like either its problem in your browser or content may be restricted in your region. You may try alternative ways to access article. – BishalG Jul 19 '18 at 07:09
  • Oh yes..... what exactly is "arithmetic only"? Which operators on what operand types are allowed? – user202729 Jul 19 '18 at 12:56
  • 1
    **Possible duplicate**: [c++ - meaning of (number) & (-number) - Stack Overflow](https://stackoverflow.com/questions/12818978/meaning-of-number-number). As this question is broader (in the sense that "it applies for more signed representation"), somebody may want to close it the reverse way. – user202729 Jul 19 '18 at 12:58
  • @user202729 What I really wanted are operations that don't rely for the correctness of the expression on the integer bit representation. I think if only `+ - / * % >> <<` but not `& | ^` are used, this would be the case. However, I now know that `i&=i-1` is equivalent to `i-=(i^-i)` *independently of the bit representation*. Thus this part of my question was not very well expressed. Ideally all this should work for unsigned (it does). – Walter Jul 19 '18 at 12:58
  • ... why is `>>` and `<<` "no bitwise manipulation"? – user202729 Jul 19 '18 at 12:59
  • Must they be applied on signed number, or unsigned can work as well? – user202729 Jul 19 '18 at 13:00
  • Are you sure that the code uses *signed* integers? Because then it’s a toss-up, whereas the code is well-defined and specified by the standard if `i` is unsigned. – Konrad Rudolph Jul 19 '18 at 13:03
  • @KonradRudolph well, initially `i>0`, so there is no difference between signed & unsigned. – Walter Jul 19 '18 at 13:04
  • @Walter Yes there **is** a difference. Especially on 1's complement machines. – user202729 Jul 19 '18 at 13:06
  • @Walter That is incorrect. Arithmetic is defined differently for signed and unsigned types in C++ and, as mentioned, the code is *well-defined* for unsigned integers (i.e. it is guaranteed to work) but it is *implementation defined* for signed integers (i.e. it may or may not work). – Konrad Rudolph Jul 19 '18 at 13:14
  • @user202729 Yes. – Konrad Rudolph Jul 19 '18 at 13:15
  • @KonradRudolph Are you saying that `i += (i&-i)` is guaranteed to work if `i` is an unsigned type? In other words, `-i` will always map to the two's complement of `i` for unsigned, no matter how signed types are represented? – Walter Jul 19 '18 at 13:21
  • 1
    In unsigned, all arithmetic operators are done modulo one plus the largest representable value. – user202729 Jul 19 '18 at 13:25
  • @Walter Yes, exactly. – Konrad Rudolph Jul 19 '18 at 13:26
  • [Finally found the answer that states that bitwise operation on unsigned is well-defined](https://stackoverflow.com/q/28591285). – user202729 Jul 19 '18 at 15:21

6 Answers6

11

The expression i & -i is based on Two's Complement being used to represent negative integers. Simply put, it returns a value k where each bit except the least significant non-zero bit of i is set to 0, but that particular bit keeps its own value. (i.e. 1)

As long as the expression you provided executes in a system where Two's Complement is being used to represent negative integers, it would be portable. So, the answer to your second question would be that the expression is dependent on the representation of negative integers.

To answer your first question, since arithmetic expressions are dependent on the data types and their representations, I do not think that there is a solely arithmetic expression that would be equivalent to the expression i & -i. In essence, the code below would be equivalent in functionality to that expression. (assuming that i is of type int) Notice, though, that I had to make use of a loop to produce the same functionality, and not just arithmetics.

int tmp = 0, k = 0;
while(tmp < 32)
{
    if(i & (1 << tmp))
    {
        k = i & (1 << tmp);
        break;
    }
    tmp++;
}
i += k;
ilim
  • 4,477
  • 7
  • 27
  • 46
10

On a Two's Complement architecture, with 4 bits signed integers:

|  i |  bin | comp | -i | i&-i | dec |
+----+------+------+----+------+-----+
|  0 | 0000 | 0000 | -0 | 0000 |   0 |
|  1 | 0001 | 1111 | -1 | 0001 |   1 |
|  2 | 0010 | 1110 | -2 | 0010 |   2 |
|  3 | 0011 | 1101 | -3 | 0001 |   1 |
|  4 | 0100 | 1100 | -4 | 0100 |   4 |
|  5 | 0101 | 1011 | -5 | 0001 |   1 |
|  6 | 0110 | 1010 | -6 | 0010 |   2 |
|  7 | 0111 | 1001 | -7 | 0001 |   1 |
| -8 | 1000 | 1000 | -8 | 1000 |   8 |
| -7 | 1001 | 0111 |  7 | 0001 |   1 |
| -6 | 1010 | 0110 |  6 | 0010 |   2 |
| -5 | 1011 | 0101 |  5 | 0001 |   1 |
| -4 | 1100 | 0100 |  4 | 0100 |   4 |
| -3 | 1101 | 0011 |  3 | 0001 |   1 |
| -2 | 1110 | 0010 |  2 | 0010 |   2 |
| -1 | 1111 | 0001 |  1 | 0001 |   1 |

Remarks:

  1. You can conjecture that i&-i only has one bit set (it's a power of 2) and it matches the least significant bit set of i.
  2. i + (i&-i) has the interesting property to be one bit closer to the next power of two.
  3. i += (i&-i) sets the least significant unset bit of i.

So, doing i += (i&-i); will eventually make you jump to the next power of two:

| i | i&-i | sum |     | i | i&-i | sum |
+---+------+-----+     +---+------+-----+
| 1 |    1 |   2 |     | 5 |    1 |   6 |
| 2 |    2 |   4 |     | 6 |    2 |  -8 |
| 4 |    4 |  -8 |     |-8 |   -8 |  UB |
|-8 |   -8 |  UB |

| i | i&-i | sum |     | i | i&-i | sum |
+---+------+-----+     +---+------+-----+
| 3 |    1 |   4 |     | 7 |    1 |  -8 |
| 4 |    4 |  -8 |     |-8 |   -8 |  UB |
|-8 |   -8 |  UB |

UB: overflow of signed integer exhibits undefined behavior.

YSC
  • 38,212
  • 9
  • 96
  • 149
6

If i has unsigned type, the expressions are completely portable and well-defined.

If i has signed type, it's not portable, since & is defined in terms of representations but unary -, +=, and -= are defined in terms of values. If the next version of the C++ standard mandates twos complement, though, it will become portable, and will do the same thing as in the unsigned case.

In the unsigned case (and the twos complement case), it's easy to confirm that i&-i is a power of two (has only one bit nonzero), and has the same value as the lowest-place bit of i (which is also the lowest-place bit of -i). Therefore:

  • i -= i&-i; clears the lowest-set bit of i.
  • i += i&-i; increments (clearing, but with carry to higher bits) the lowest-set bit of i.

For unsigned types there is never overflow for either expression. For signed types, i -= i&-i overflows taking -i when i initially has the minimum value of the type, and i += i&-i overflows in the += when i initially has the max value of the type.

R.. GitHub STOP HELPING ICE
  • 208,859
  • 35
  • 376
  • 711
5

Here is what I researched prompted by other answers. The bit manipulations

i -= (i&-i);   // strips off the LSB (least-significant bit)
i += (i&-i);   // adds the LSB

are used, predominantly, in traversing a Fenwick tree. In particular, i&-i gives the LSB if signed integers are represented via two's complement. As already pointed out by Peter Fenwick in his original proposal, this is not portable to other signed integer representations. However,

i &= i-1;      // strips off the LSB

is (it also works with one's complement and signed magnitude representations) and has one fewer operations.

However there appears to be no simple portable alternative for adding the LSB.

Walter
  • 44,150
  • 20
  • 113
  • 196
  • @DavidFoerster because `i &= ~1` and `i &= i - 1` are very different, one is to get the least significant bit, one is to get the least significant **set** bit – phuclv Jul 19 '18 at 14:31
  • [Here is a visual representation of Fenwick tree](https://stackoverflow.com/a/35887846/995714) – phuclv Jul 19 '18 at 14:34
  • @DavidFoerster I know. A lot of word usage on this question is incorrect – phuclv Jul 19 '18 at 14:35
  • The portable way to add the bit is `i += (i & -(unsigned)i)`. To obfuscate it just use [`i & (i ^ (i - 1))`](https://stackoverflow.com/q/24772669/995714) – phuclv Jul 19 '18 at 15:01
  • @phuclv with the figures stolen from Fenwicks original publication :-) – Walter Jul 19 '18 at 15:51
3

i & -i is the easiest way to get the least significant bit (LSB) for an integer i.
You can read more here.
A1: You can read more about 'Mathematical Equivalents' here.
A2: If the negative integer representation is not the usual standard form (i.e. weird big integers), then i & -i might not be LSB.

Sirawit 'Plum' P.
  • 271
  • 1
  • 8
  • 4
    There is no such thing as a standard form for bit-representing negative integers. Yes, almost all hardware these days uses two's complement, but AFAIK, the language standard does not require that. – Walter Jul 19 '18 at 06:34
  • Yes, maybe I used wrong words. If the representation is not in the two's complement, the output would be different. – Sirawit 'Plum' P. Jul 19 '18 at 06:41
  • @DavidFoerster is right, it's the way to get the rightmost set bit (in the non-negative bit pattern). And the cross-platform way to do that regardless of signed type representation is `i & -(unsigned)i` because unsigned maths are reduced modulo 2^n – phuclv Jul 19 '18 at 14:28
0

The easiest way to think of it is in terms of the mathematical equivalence:

-i == (~i + 1)

So -i inverts the bits of the value and then adds 1. The significance of this is that all the lower 0 bits of i are turned into 1s by the ~i operation, so adding 1 to the value causes all those low 1 bits to flip to 0 whilst carrying the 1 upwards until it lands in a 0 bit, which will just happen to be the same position as the lowest 1 bit in i.

Here's an example for the number 6 (0110 in binary):

i = 0110
~i == 1001
(~i + 1) == 1010
i & (~i + 1) == 0010

You may need to do each operation manually a few times before you realise the patterns in the bits.

Here's two more examples:

i = 1000
~i == 0111
(~i + 1) == 1000
i & (~i + 1) == 1000

i = 1100
~i == 0011
(~i + 1) == 0100
i & (~i + 1) == 0100

See how the + 1 causes a sort of 'bit cascade' carrying the one up to the first open 0 bit?

So if (i & -i) is a means of extracting the lowest 1 bit, then it follows that the use cases of i += (i & -i) and i -= (i & -i) are attempts to add and subtract the lowest 1 bit of a value.

Subtracting the lowest 1 bit of a value from itself serves as a means to zero out that bit.

Adding the lowest 1 bit of a value to itself doesn't appear to have any special purpose, it just does what it says on the tin.

It should be portable on any system using two's complement.

Pharap
  • 3,826
  • 5
  • 37
  • 51