AdHominem - 1 month ago 11
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.

`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).