2

I found an interesting property about 1's complement when reading an interview preparation book.

The property says given a number X, we can generate a mask that shows the first set bit (from right to left) using the 1's complement as follows: X & ~(X - 1) where ~ stands for 1's complement.

For example, if X = 0b0011 then 0b0011 & 0b1101 = 0b0001

I understood that the author is doing the X-1 to flip the first non-zero bit from the right. But I'm curious as to how did he come up with the idea that taking a 1's complement of X-1 and &ing it with X would result into a bit-mask that shows the first non-zero bit in X.

Its my first time posting at StackOverflow, so my apologies if this question doesn't belong here.

OmniShiva
  • 21
  • 2
  • Possible duplicate of [n & ~(n - 1) What does this function do?](http://stackoverflow.com/questions/21502303/n-n-1-what-does-this-function-do) – phuclv Nov 07 '16 at 02:54

3 Answers3

2

First, notice that for any X, X & (~X) = 0 and X & X = X.

Let X = b_n b_(n-1) ... b_k ... b_1, where b_k is the first set bit.
Thus, X is essentially this:
    b_n   b_(n-1) ...  b_(k+1) 1 0 0 ... 0
                               ---- k ----
X-1 is:
    b_n   b_(n-1) ...  b_(k+1) 0 1 1 ... 1
                               ---- k ----
~(X-1) is:
    ~b_n ~b_(n-1) ... ~b_(k+1) 1 0 0 ... 0
                               ---- k ----

X & ~(X-1) is:
    0 0 .................... 0 1 0 0 ... 0
                               ---- k ----
Yun-Chih Chen
  • 543
  • 6
  • 18
1

This can actually be proved using some math. Let x be a positive integer. For all x, there exists a binary representation of x. Additionally, for all x there exists a number x - 1 which also has a binary representation. For all x, the bit in the 1s place, will differ from that of x - 1. Let us define ~ as the ones' complement operator. For any binary number b, ~b turns all of the 0s in b into 1s, and all of the 1s in b into 0s. We can then say that ~(x - 1) must then have the same bit in the 1s place as x. Now, this is simple for odd numbers as all odd numbers o have a 1 in the 1s bit, and so must ~(x - 1), and we can stop there. For even numbers this gets a bit trickier. For all even numbers, e, the 1 bit must be empty. As we stated that x (and also e) must be greater than 0, we can also say that for all even numbers, e, there exists some bit such that the value of that bit is 1. We can also say that for e - 1, the 1s bit must be 1 as e - 1 must be odd. Additionally, we can say that the first bit with a value of 1 in e will be 0 in e - 1. Therefore, using the ones' complement of e - 1, that bit in e that must have been 0, will become 1 by the rules of ones' complement. Using the & operator, that will be the common 1 bit between e and ~(e - 1).

Eli Sadoff
  • 7,173
  • 6
  • 33
  • 61
1

This trick is probably better known written as

X & -X

which is by definition (of -) equivalent, and using the following interpretation of - it becomes very simple to understand:

In string notation for a number that isn't zero, -(a10k) = (~a)10k

If you're unfamiliar with the notation, a10k just means "some string of bits 'a' followed by a 1 followed by k zeroes".

This interpretation just says that negation keeps all the trailing zeroes and the lowest 1, but inverts all higher bits. You can see that it does that from the definition of negation as well, for example if you look at ~X + 1, you see that the +1 cancels out the inversion for the trailing zeroes (which become ones which the +1 carries through) and the lowest set bit (which becomes 0 and then the carry through the trailing zeroes is captured by it).

Anyway, using that interpretation of negation, obviously the top part is removed, the lowest set bit is kept, and the trailing zeroes are just going to stay.

In general, the string notation is very helpful when coming up with these tricks. For example if you know that negation looks like that in string notation, this trick is really quite obvious, and so are some related tricks which you can then also find:

  • x & x - 1 resets the lowest set bit
  • x | -x keeps the trailing zeroes but sets all higher bits
  • x ^ -x keeps the trailing zeroes, resets the lowest set bit, but sets all higher bits

.. and more variants.

harold
  • 61,398
  • 6
  • 86
  • 164
  • Unfortunately, this version is undefined in C. – apt1002 Nov 07 '16 at 02:34
  • @apt1002 not if you use unsigned numbers, and anyway I don't see a C tag here – harold Nov 07 '16 at 02:36
  • Even then: http://stackoverflow.com/questions/3952123/representation-of-negative-numbers-in-c . You're right there's no C tag; I was inferring why the OP chose the form he did, perhaps incorrectly. – apt1002 Nov 07 '16 at 02:40
  • Ah, my apologies, I misread your comment. You appear to be right about unsigned negation. – apt1002 Nov 07 '16 at 02:41
  • @apt1002 now that we're talking about C anyway - if that was the reasoning, does it help? I'm not extremely familiar with C's UB nonsense, but that -1 is already unsafe and IIRC the complement is allowed to create an invalid value – harold Nov 07 '16 at 02:51
  • It's arguable. Yes, the result is undefined if X==0, but that's actually what you want in this case! Your suggestion of using unsigned negation is better. – apt1002 Nov 07 '16 at 03:03