Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Meaning of bitwise and(&) of a positive and negative number?

Can anyone help what n&-n means?? And what is the significance of it.

like image 761
Shubham Tyagi Avatar asked Mar 13 '13 20:03

Shubham Tyagi


1 Answers

N&(-N) will give you position of the first bit '1' in binary form of N. For example:

N = 144 (0b10010000) => N&(-N) = 0b10000
N = 7 (0b00000111) => N&(-N) = 0b1

One application of this trick is to convert an integer to sum of power-of-2. For example:

To convert 22 = 16 + 4 + 2 = 2^4 + 2^2 + 2^1
22&(-22) = 2, 22 - 2 = 20
20&(-20) = 4, 20 - 4 = 16
16&(-16) = 16, 16 - 16 = 0
like image 75
Thanh Cong Vu Avatar answered Oct 02 '22 22:10

Thanh Cong Vu