CODEWITHSUNDEEP
mathassemblybinarybit-manipulationarithmetic-expressions
Abhas Kumar Sinha
Abhas Kumar Sinha

Reputation: 183

How does the formula x & (x - 1) works?

From Hacker's Delight: 2nd Edition:

Formula to turn off the rightmost 1-bit of a word.

The formula here seems a little bit awkward here. How is some x vector is subtracted from 1 vector (presumbly 0x1111 1111) when x is smaller than 1? (Like: (as given in example) 0x0101 1000 - 0x0000 0000 doesn't make any sense to me) The former is a smaller number than the first one and the words aren't storing signed vectors either. Is that something related to RISC specific here or what?

As specified in the notation section of the book. A bold letter corresponds a vector for word like x = 00000000. And a bold one differs from a light face 1. As bold 1 = 11111111 which is an 8 bit word.

Edit2: Special Thanks to Paul Hankin to figure out the unconventional notations used here. A bold faced one refers to 32 bit size word which is [00000001] and a light faced 1 refers to a number one as in C.

Upvotes: 7

Views: 9921

Answers (3)

Shrey Singh
Shrey Singh

Reputation: 41

According to the Brian Kernighan's Algorithm which is used for counting the set bits in a given number, subtracting 1 from a number x will invert all the bits from it's rightmost set bit.

Let,

x = 14, which is 1110 in binary. Here, 2nd bit from right is the rightmost set bit.

x - 1 = 13, which is 1101 in binary. It is clearly observed that the bits from 2nd bit from right are inverted.

Now, if we do a bitwise AND operation on these two numbers, i.e., x & (x-1) we will unset the bits from the rightmost set bit of number x. Take a look at the below example,

    1 1 1 0      (14)      
&   1 1 0 1      (13)

    1 1 0 0      (12)

If, the number x is originally a power of 2, then doing bitwise AND with (x-1) will result in 0. For example,

    1 0 0 0      (8)      
&   0 1 1 1      (7)

    0 0 0 0      (0)

This is because, the number x, which is a power of 2, only has a single set bit in its binary representation.

Similarly, if we try doing the bitwise AND of a number x with the bitwise NOT of number (x-1), then it will only set the rightmost bit in the resultant number. i.e., x & [~(x-1)]. Check below example,

x = 14
x - 1 = 13

Hence, ~(x-1) will be,

    1 1 0 1      (13)      
    0 0 1 0      (~13)

NOTE : The term ~(x-1) will evaluate to -x. The explanation for the same is provided here

Therefore,

    1 1 1 0      (14)      
&   0 0 1 0      (~13)

    0 0 1 0      (2)

The 2nd bit from the right which was the rightmost set bit in binary representation of number x which is 14, is the only set bit in the resultant number. Also, is a power of 2, since there is only single set bit in the result.

Upvotes: 4

MrSmith42
MrSmith42

Reputation: 10161

Let's take a look at an what x-1 does. Assume x is a value '???? 1000 (? are 0 or 1)
=> x-1 = ???? 0111
=> x & (x-1) = ???? 0000

It's very similar no matter where the right most 1 is placed within x.

Requested example:
x=00001111
=> x-1=00001110
=> x & (x-1) = 00001110

P.s. x-1 = 00001110 - 00000001 (<=> 00001110 + 11111111)

Upvotes: 4

Stef
Stef

Reputation: 15525

Subtracting 1

Since we're more familiar with decimal than with binary, it sometimes helps to look at what happens in decimal.

What happens when subtracting 1 in decimal? Take for example 1786000 - 1 = 1785999.

If you subtract 1 from a positive number x in decimal:

  • all the zeroes at the right of x become 9;
  • the rightmost nonzero digit of x becomes 1 less;
  • other digits are unaffected.

Now, in binary, it works exactly the same, except we only have 0 1 instead of 0 123456789.

If you subtract 1 from a number x in binary:

  • all the zeroes at the right of x become 1;
  • the rightmost nonzero bit of x becomes 0;
  • other bits are unaffected.

What about negative numbers? Happily, representation using 2's complement is such that negative numbers behave exactly like positive numbers. In fact, when looking at the bits of x, you can subtract 1 from x without needing to know whether x is a signed int or an unsigned int.

x & (x-1)

Let's start with an example: x = 01011000. We can subtract 1 the way I just explained:

x   = 01011000
x-1 = 01010111

Now what's the result of the bitwise-and operation x & (x-1)? We take the two bits in each column; if they are both 1, we write 1; if at least one of them is 0, we write 0.

x       = 01011000
x-1     = 01010111
x&(x-1) = 01010000

What happened?

  • all the zeroes at the right of x remain zero;
  • the rightmost 1 of x becomes a 0 because of x-1;
  • all other bits are unaffected, because they are the same in x and x-1.

Conclusion: we have zeroed the rightmost 1 of x, and left all other bits unaffected.

Upvotes: 9

Related Questions