Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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?

like image 426
Piyush Soni Avatar asked Dec 12 '17 19:12

Piyush Soni


People also ask

What does bitwise and operation do?

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.

What Bitwise operation means?

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.

What is N &( n 1 in bit manipulation?

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)); } };


1 Answers

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.

like image 124
jxh Avatar answered Oct 18 '22 12:10

jxh