2

Given a number n, the bit wise operation n & (n - 1) always produces a number that is 1 bit away from n. Below are some examples:

n = 4 => b'100' & b'011' = b'000'
n = 5 => b'101' & b'100' = b'100'
n = 6 => b'110' & b'101' = b'100'

In other words, n & (n - 1) always clears 1 bit from n. Why is this? Can someone provide a proof?

trincot
  • 317,000
  • 35
  • 244
  • 286
bli00
  • 2,215
  • 2
  • 19
  • 46
  • Please [edit] your questions to include what you have tried so far? Where do you stuck in your proof? – Progman Dec 18 '19 at 19:31
  • there are a lot of duplicates: [Why does (x-1) toggle all the bits from the rightmost set bit of x?](https://stackoverflow.com/q/50869508/995714), [n & (n-1) what does this expression do?](https://stackoverflow.com/q/4678333/995714), [How does this line work? n=n&(n-1)](https://stackoverflow.com/q/15370250/995714), [What does the bitwise code “$n & ($n - 1)” do?](https://stackoverflow.com/q/1551500/995714) – phuclv Dec 19 '19 at 00:09
  • Yes. I closed the thread. – bli00 Dec 19 '19 at 05:53
  • 1
    I'm voting to reopen this post as the linked threads doesn't exactly answer the question I proposed. The links provided answers the questions "what does n & (n-1) do?" And all of the answers says "it tests whether if n is a power of 2". My question is asking "why n & (n-1) clears 1 bit from n". An answer to this doesn't exactly follow from knowing whether if n is a power of 2. – bli00 Dec 20 '19 at 02:01
  • this question [How does this line work ? n=n&(n-1)](https://stackoverflow.com/a/15370410/995714) already states that why the last 1 bit is cleared. It doesn't say anything about power of 2 (to check that you need another comparison with 0) – phuclv Dec 21 '19 at 10:02
  • [what is the means of i &=(i-1)](https://stackoverflow.com/q/38644840/995714) – phuclv Dec 21 '19 at 10:07

1 Answers1

6

Some preliminary remarks:

  • The statement is true for when n is non-zero. There must be at least one 1-bit.
  • A bitwise AND-operation copies the bits that are the same in both operands (1&1==1 and 0&0==0), and produces a zero bit when the corresponding bits are different (1&0==0 and 0&1==0).

Subtraction of 1 is easy when n is odd: you just clear that final 1-bit and you're done. When n is not odd, you need to "borrow" from an adjacent bit, which leads to a potential cascade of borrowing, until you find a 1-bit you can borrow from (See American method for manual subtraction on Wikipedia). This means that starting from the right (at the least significant bit of n), you flip bits one by one, until the first 1-bit is encountered, which is also flipped.

So in a subtraction you flip a group of bits which includes exactly one 1-bit, which by consequence is the only one that gets flipped to a 0-bit.

As the bit-wise AND-operation on n will produce a 0 for every bit that was flipped for getting n-1, but will keep any other bit of n as it was before, it actually clears one 1-bit of n.

From this follows also that the bit that is cleared, is always the least significant 1-bit in n.

trincot
  • 317,000
  • 35
  • 244
  • 286