CODEWITHSUNDEEP
algorithmperformancemath
clb
clb

Reputation: 723

Determining whether a number contains a given power of two in its sum

Very badly worded title, but I couldn't think of how to summarise the problem.

Essentially, every number can be formed by adding powers of two where each number appears at most once. e.g. 20=16+4, 27=16+8+2+1, etc.

What's the most efficient way of determining whether a given number occurs in this decomposition of another number?

It wouldn't be too hard to simply calculate the full set of numbers to be added, and see if the number appears in that. But there must be some kind of shortcut, right? Calculating the whole set seems overkill when I just need to verify the presence of a given number.

Upvotes: 1

Views: 230

Answers (3)

Aman
Aman

Reputation: 8995

List of powers of 2 that form the number:

[2 ** (31 - i) for i, j in enumerate('{0:032b}'.format(x)) if j == '1']

and then you can do a membership test with in. 

>>> x
27
>>> [2 ** (31 - i) for i, j in enumerate('{0:032b}'.format(x)) if j == '1']
[16, 8, 2, 1]
>>> 4 in [2 ** (31 - i) for i, j in enumerate('{0:032b}'.format(x)) if j == '1']
False

Where

  • '{0:032b}'.format(x) formats the number as a 32-bit binary string.

  • enumerate('{0:032b}'.format(x)) is used to assign an index to each bit.

  • We then look for bits that are 1 (j == '1'), and extract the corresponding power of 2 2 ** (31 - i).

Upvotes: 1

Blorgbeard
Blorgbeard

Reputation: 103525

You are asking how to check whether a particular bit is set.

The question "does the number 2**x appear in the decomposition of y?" is equivalent to the question "is bit x set in the binary representation of y?".

So you can use bitwise operators to check - pseudo-code:

bit_is_set = (y & 2**x != 0)

Upvotes: 3

displayName
displayName

Reputation: 14389

  • Get the binary representation of the number.
  • See if the bit that represents the power of 2 you are looking for, is set or not.

Example:

To find whether 256 (= 1000000002) is made up of 4 ( = 1002), see that the 3rd bit of binary representation of 256 is set or not. In this case it is not set.

Also, see that 260 (= 100001002) is indeed made of 4 because its 3rd bit is set.

Upvotes: 1

Related Questions