2
$\begingroup$

I'm trying to understand the complexity/number of iterations needed to determine the number of bits in an integer.

4 = 100  =  3 bits
3 = 011  =  2 bits
8 = 1000 =  4 bits

I skimmed through this article and it says: A positive integer n has b bits when 2^b-1 ≤ n ≤ 2^b – 1

But when you do the math for an integer 4, you get 2.32 ~= 2. What am I doing wrong?

Improve this question
$\endgroup$
2
$\begingroup$

The number of bits is always an integer, so you have to solve for that equation over the integers. Thus, use $\lceil \lg (n+1) \rceil$.

Improve this answer
$\endgroup$
3
  • $\begingroup$ not sure if I understand. do you see anything wrong with the wolfram alpha's solution? $\endgroup$ – xyf Sep 17 '20 at 16:25
  • $\begingroup$ @xyf You have to round up what wolfram alpha gave. So you get 3. That's because of the way the inequality goes in your formula: $n \le 2^b - 1$ $\endgroup$ – 6005 Sep 18 '20 at 1:53
  • $\begingroup$ Why round up though? Does it have to do with inequality? $\endgroup$ – xyf Sep 18 '20 at 2:20
1
$\begingroup$

Some answers suggest using the logarithm of n.

Now guess what is the first thing your computer does if you try to calculate log n: It converts n from an integer to a floating point number, and from the exponent of the floating point number you get the number of bits immediately. So whatever time complexity there is, you have spent it already before even trying to calculate the logarithm. Just be converting the integer n to a floating point number.

You also don't need to calculate the logarithm, which is very time consuming, just look at the exponent field in the floating point representation.

Assuming you are given a 64 bit integer:

count = 1
if any bit in (n & 0xffff ffff 0000 0000) is set then count = 32 and n = (n >> 32), count = count + 32.
if any bit in (n & 0xffff 0000) is set then count = count + 16 and n = (n >> 16).
if any bit in (n & 0xff00) is set then count = count + 8 and n = (n >> 8).
if any bit in (n & 0xf0) is set then count = count + 4 and n = (n >> 4).
if any bit in (n & 0x0c) is set then count = count + 2 and n = (n >> 2).
if any bit in (n & 0x02) is set then count = count + 1.

For a number that is stored in 2^k bits, this takes O(k).

Improve this answer
$\endgroup$
0
$\begingroup$

N is 4 and b is 3. The formula holds perfectly fine. Nothing is wrong.

The reason to "round up" in the context of the numbers you have is because of the inequality. 2 would not satisfy x ≥ ~2.32. But 3 would.

Improve this answer
$\endgroup$
6
  • $\begingroup$ looks like you didn't look at the example I posted... $\endgroup$ – xyf Sep 18 '20 at 1:42
  • $\begingroup$ Not sure why you think that. Your quote is is "A positive integer n has b bits when 2^b-1 ≤ n ≤ 2^b – 1." That formula is holding. I also went to your Wolfram link, but I honestly don't understand how you got from one to the other. Anyway, n and b are direct references to the exact inequality you posted, and it holds exactly as you posted it. So I'm still unclear what you think the problem is, or where 2.32 is coming from. $\endgroup$ – recursive Sep 18 '20 at 2:03
  • $\begingroup$ do you see why 2.32 is rounded up to 3? $\endgroup$ – xyf Sep 18 '20 at 2:20
  • $\begingroup$ No. I don't see why 2.32 would be rounded up to 3. I also don't know where 2.32 came from. I also note that rounding was never mentioned in the inequality. $\endgroup$ – recursive Sep 18 '20 at 2:50
  • $\begingroup$ I might have figured out what you're asking. In the Wolfram link, it says x ≥ log(5) / log(2). So you perhaps 2.32 is a reference to the right hand side of that inequality. If that's the case, x is the number of bits, and it's greater than or equal to 2.32. So that's the reason it's rounded up in that context. $\endgroup$ – recursive Sep 18 '20 at 2:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.