Most efficient way to check if only one '1' exists in binary representation of a decimal number

Question

What is the most efficient (in terms of speed and space) way to check if a decimal number only has a single '1' in its binary representation without using special functions (math, numpy, etc.)?

e.g. 1 is '001' and 4 is '100'.

I've tried this

binary  =  "{0:b}".format(value)
if binary.count('1') != 1:
    return 1
else:
    return 0

I believe this is O(log n) in terms of space and O(n) in terms of speed? Is there a way to do this more efficiently?

That's not actually a "decimal number", by the way. Calling `str` produces a decimal string, but an int semantically just represents a number with no base attached, and the internal representation is binary. — user2357112, Nov 10 '19 at 04:42
per the link for @awesoon: `(x != 0) and ((x & (x - 1)) == 0)` is about as fast as using `math.log2()` — Mark, Nov 10 '19 at 04:43
`math.log2` loses precision due to the use of floating point, so it produces false positives for integers close enough to a large power of 2. — user2357112, Nov 10 '19 at 04:44
Interesting and good point @user2357112. Easy enough to see with something like `math.log2(2 ** 420+1).is_integer()` — Mark, Nov 10 '19 at 04:45

score 1 · Answer 1 · answered Nov 10 '19 at 04:56

1

One of the method to do it could be-

binary_num = '00101010'
result = [1 for x in binary_num if x == '1']
if len(result) == 1:
    print('Success')
else:
    print('Failed')

answered Nov 10 '19 at 04:56

Chetan Goyal

435
5
14

Most efficient way to check if only one '1' exists in binary representation of a decimal number

1 Answers1