AdHominem AdHominem - 10 months ago 57
C Question

Is it true that the amount of necessary binary digits for any given positive integer is ceil( log_2 n)?

Title pretty much says it. I can only guess but I have no proof that this holds. In Python

math.ceil(math.log(n) / math.log(2))

Context: I'm creating a intbyte-to-char*binary function which only displays the necessary digits (id est no trailing zeros), thus I would need to dynamically allocate memory for the char array. However I assume there exists an upper bound which I could use to determine the length statically.

Edit: It seems my approach was wrong. To check the amount of digits necessary, it is way faster just to divide the number by 2 successively until it is 0 and keep track of the amount of divisions.

Answer Source

The formula is almost correct but you'll be out by one digit for exact powers of 2. The formula

1 + math.floor(math.log(n) / math.log(2))

would, I think, work better. But I wouldn't dwell on that too much simply because I'd never rely on a computer to compute math.floor(math.log(n) / math.log(2)) without the risk of the result being one less due to imprecision centred around floating point and the computation of a log: for the latter you're at the mercy of your chipset.

Testing the length by repeated integer division by 2 until zero is attained would be more robust, and possibly faster. log is not a cheap function computationally. You could even use the flashy bit fiddle x & (x - 1) (Google it).