CODEWITHSUNDEEP
c++cbit-manipulationbitwise-operators
Piyush Soni
Piyush Soni

Reputation: 197

What does bitwise operation n&(n-1) do?

I was trying to understand some code, wherein I found the statement:

n=n&(n-1);

What does this do?

Upvotes: 5

Views: 4030

Answers (1)

jxh
jxh

Reputation: 70362

That equation zeroes out the least significant non-zero bit in n.

If we assume 8 bits, then here is the back of the envelop explanation. Let n be 70.

n       = 01000110
n-1     = 01000101
          --------
n&(n-1) = 01000100

As a consequence, if the result is 0, it means there was only one bit set in n originally, which means it was a power of 2 (or it was 0 to being with).

If applied iteratively in a loop until n becomes 0, the number of iterations counts the number of bits set in n originally. However, most processors will have a built-in operation to do this for you.

If bit-hacks interest you generally, searching this site for "bithacks" generates many hits.

Upvotes: 14

Related Questions