Innovative way for checking if number has only one on bit in signed int

Question

I'm looking for an innovative way to check if a number has only one on bit in a signed int.

I am well aware that I can simply do a loop with a counter, some modular division, and a bit shift. But I'm curious if there is a better way since we are only looking for ONE bit to be on.

bool HasOnlyOneBit (int  numb)
{
   //return true if numb has only one bit (I.E. is equal to 1, 2, 4, 8, 16... Int.MinValue)
}

Innovative? You mean, something that uses genetic algorithms that cloud compute on quantum computers? — P Shved, Jul 01 '10 at 20:22
Possible duplicate of [Check if only one single bit is set within an integer (whatever its position)](http://stackoverflow.com/questions/13420241/check-if-only-one-single-bit-is-set-within-an-integer-whatever-its-position) — phuclv, Nov 04 '15 at 15:41

score 45 · Accepted Answer · edited Jul 01 '10 at 18:54

return x == (x & -x);

This answer works because of the way two's complement notation is designed.

First, an example. Assume we have 8-bit signed integers.

00010000  =  16
11110000  = -16

The bitwise and will give you 00010000 as a result, equal to your original value! The reason that this works is because when negating in 2's complement, first invert all the bits, then add 1. You'll have a bunch of zeros and a bunch of carries until a one falls into place. The bitwise and then checks if we have the right bit set.

In the case of a number that isn't a power of two:

  00101010  =  42
& 11010110  = -42
----------
  00000010 !=  42

Your result will still have only a single bit, but it won't match the original value. Therefore your original value had multiple bits set.

Note: This technique returns true for 0, which may or may not be desirable.

You also need to test for `x > 0`, since this expression returns true for `x == 0`, but 0 is not a power of 2. — Paul R, Jul 01 '10 at 20:33
just be careful, this won't work for 0, you need to handle it by itself — K'', Oct 30 '16 at 18:58

bragboy · Answer 2 · 2017-06-02T09:53:46.537

25

This is a famous problem

(x & x-1) == 0

Power of 2 from Wiki : here

64 = 01000000 (x)
63 = 00111111 (x-1)
______________
&  = 00000000  == 0
______________

Case when some other bits are ON

18 = 00010010 (x)
17 = 00010001 (x-1)
______________
&  = 00010000  != 0
______________

edited Jun 02 '17 at 09:53

answered Jul 01 '10 at 18:41

bragboy

34,892
30
114
171

1

take care of edge case where x!=0 – yesraaj Jul 07 '10 at 18:49
2

sorry I meant when x=0 --> x & (x - 1) --> 0 , so instead of false it returns true! – yesraaj Jul 08 '10 at 15:59
1

The code is correct, but the explanation is wrong. 18 & 17 is 16, not 19 as you suggest. – George Polevoy Oct 01 '15 at 13:41

score 8 · Answer 3 · edited Jul 01 '10 at 20:14

8

I'd recommend you take a look at the Bit Twiddling Hacks page and choose the most suitable option under "Determining if an integer is a power of 2" or "Counting bits set".

edited Jul 01 '10 at 20:14

Pete Kirkham

48,893
5
92
171

answered Jul 01 '10 at 18:40

Kaleb Pederson

45,767
19
102
147

score 2 · Answer 4 · answered Jul 01 '10 at 19:35

2

return (x && ((x & x-1) == 0))

answered Jul 01 '10 at 19:35

srikanta

2,914
3
21
35

score 1 · Answer 5 · answered May 11 '15 at 11:56

return (x && (0x8000000000000000ULL % x));

This is a simplification of the following code:

if (x == 0) {
    return false;
} else if (0x8000000000000000ULL % x) {
    return false;
} else {
    return true;
}

Explanation: 0x8000000000000000 is the highest "1 bit only" value for an 64 bit register. Only a division by an other "1 bit only" value will result in no remainder.

score 0 · Answer 6 · answered Jul 01 '10 at 18:41

0

Take the log to base 2 of your number, if it's an integer your number has only 1 1 bit. Not sure that I think this is better than any of your excluded options.

answered Jul 01 '10 at 18:41

High Performance Mark

77,191
7
105
161

score 0 · Answer 7 · answered Mar 19 '20 at 12:00

0

Python3 memory-efficient solution

return n > 0 and (n & (n-1)) == 0

answered Mar 19 '20 at 12:00

Shyambeer Singh

318
2
9

Innovative way for checking if number has only one on bit in signed int

7 Answers7

Linked