Menu
I was trying to understand some code, wherein I found the statement:
n=n&(n-1);
What does this do?
426
The bitwise AND operator ( & ) compares each bit of the first operand to the corresponding bit of the second operand. If both bits are 1, the corresponding result bit is set to 1. Otherwise, the corresponding result bit is set to 0.
Bitwise is a level of operation that involves working with individual bits which are the smallest units of data in a computing system. Each bit has single binary value of 0 or 1. Most programming languages manipulate groups of 8, 16 or 32 bits. These bit multiples are known as bytes.
Last Edit: October 24, 2018 9:34 PM. 75.5K VIEWS. Power of 2 means only one bit of n is '1', so use the trick n&(n-1)==0 to judge whether that is the case. class Solution { public: bool isPowerOfTwo(int n) { if(n<=0) return false; return !(n&(n-1)); } };
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.
124
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
