CODEWITHSUNDEEP
algorithmbit-manipulation
user466534
user466534

Reputation:

Using bit manipulation to tell if an unsigned integer can be expressed in the form 2^n-1

To test if an unsigned integer is of the form 2^n-1 we use:

x&(x+1)

What is that supposed to equal? That is,

x&(x+1) == ?

Upvotes: 6

Views: 309

Answers (3)

Pascal Cuoq
Pascal Cuoq

Reputation: 80274

In complement to the existing answers, here is a short explanation of why numbers x that are not of the form 0b00000 (zero) or 0b0111..11 (all lowest digits set, these are all the numbers 2^n-1 for n>0) do not have the property x&(x+1) == 0.

For a number x of the form 0b????1000..00, x+1 has the same digits as x except for the least significant bit, so x & (x+1) has at least one bit set, the bit that was displayed as being set in x. By way of shorter explanation:

x       0b????1000..00
x+1     0b????1000..01
x&(x+1) 0b????10000000

For a number x of the form 0b????10111..11:

x       0b????10111..11
x+1     0b????110000000
x&(x+1) 0b????10000..00

In conclusion, if x is not either zero or written in binary with all lowest digits set, then x&(x+1) is not zero.

Upvotes: 6

James McNellis
James McNellis

Reputation: 355079

A number of the form 2^n-1 will have all of the bits up to the nth bit set. For example, 2^3-1 (7) is:

0b0111

If we add one to this, we get 8:

0b1000

Then, performing a bitwise and, we see that we get zero, because no bit is set on in both numbers. If we start with a number not of the form 2^n+1, then the result will be nonzero.

Upvotes: 7

JustJeff
JustJeff

Reputation: 12980

Zero. If X is 2^N-1, it is an unbroken string of 1's in binary. One more than that is a 1 followed by a string of zeroes same length as X, so the two numbers have no 1 bits in common in any location, so the AND of the two is zero.

Upvotes: 5

Related Questions