CODEWITHSUNDEEP
c++11bitwise-operators
yagyanshbhatia
yagyanshbhatia

Reputation: 31

Bit wise AND to calculate largest power of two that divides 'n' - C++

While reading Binary indexed tree I came across the following expression that magically calculated the largest power of two that divides a given number 'n'

n&-n

I'd like a formal argument why this expression is doing what it does. Also, there are many tricks like this using bitwise operator that might save us a lot of time and come in handy. Please list as many as you know.
For example, 1 << n gives two raised to power n.

Upvotes: 0

Views: 183

Answers (1)

yagyanshbhatia
yagyanshbhatia

Reputation: 31

Answering my own question, I wasn't able to find a very sophisticated solution but this satisfied me
Let the highest power of two that divides n be 2k.
This means there are k zeroes after the last 1(if there none, it gives n=0 and n&-n is also zero, which is correct).

-n = ~n+1, hence all digits in n are inverted except the last one and the following k zeroes.

Taking Bitwise AND will result in the last one followed by k zeroes, which is precisely 2k.
Some of the hacks using bitwise operators I found are:

x | (1 << k) sets kth bit to one

x & ~(1 << k) sets kth bit to zero

x ^ (1 << k) inverts the kth bit

x & (x−1) sets the last one bit of x to zero

x &−x sets all the one bits to zero, except for the last one bit.

positive number x is a power of two exactly when x & (x−1) = 0.

The formula x | (x−1) inverts all the bits after the last one bit

These can be justified with similar proofs. I'll add more as I come across more.

Upvotes: 2

Related Questions