One-liner for checking if integer is of form 2^1-2^j using bitwise operators_问答_开发者

One-liner for checking if integer is of form 2^1-2^j using bitwise operators

开发者 https://www.devze.com 2022-12-16 22:22 出处：网络

I want a one line code to check whether a given integer is of form 2i - 2开发者_StackOverflow社区j or NOT. (using bitwise operators)As AndreyT says, the answer can be found in Hacker\'s Delight:

I want a one line code to check whether a given integer is of form 2ⁱ - 2^{开发者_StackOverflow社区j} or NOT. (using bitwise operators)

As AndreyT says, the answer can be found in Hacker's Delight:

Use the following formula to turn off the rightmost contiguous string of 1-bits (e.g., 01011000 ⇒ 01000000):
((x | (x – 1)) + 1) & x
This may be used to see if a nonnegative integer is of the form 2^j – 2^k for some j ≥ k ≥ 0; apply the formula followed by a 0-test of the result.

(was debating whether to post this, as it's a homework question, but as AndreyT already mentioned it and it's easily Googlable, I figure it's more helpful to quote directly; I'll let the questioner deal with the ethical implications of accepting help on the homework, and I expect that if his answer depends on this, he will write up the explanation of how it works himself)

A hint or two:

Other have pointed out that what you're looking for is a number that consists of a string of ones followed by a string of zeros.

If you flip all the bits in this, you'll get a string of 0's followed by a string of 1's. If you increment that, all the one bits will become zeros, and exactly one bit above those will become a one.

If you AND those last two together, you'll get zero.

In binary, a power of two is a number of the form 100...0 (A 1 followed by x 0s, where x is the exponent)

Therefore, any binary number of the form 2ⁱ - 2^j will be a string of 1s followed by a string of 0s.

Windows Calculator (in binary mode) is a great way to experiment with this.

Let's take a look at this for a moment. If i=j, then the answer is checking to see if the integer is 0. Otherwise, the key is to see how often the bits toggle I think as what you want to see is if all the 1s are together as a group, collectively, as really the arithmetic here is quite simple. If the toggle is 2 then it is of that form.

Left shift until you get a 0, once u get a zero, u should not get 1 again