3 ms·
> Given an integer n, what is the number of bits required to represent every integer in the range -n..n ? (log n) + 1
by lmm 2y ago
> Given an integer n, what is the number of bits required to represent every integer in the range -n..n ?
(log n) + 1
- maggit 2y agoThat's true for normal binary encoding of integers, but I think we should understand the question in context of the post: What's the number of bits required in iterated log coding?
- yorwba 2y agoEmpirically, it seems to grow more like 2*log2(n)+1. A handwavy argument can be made that the first bit serves to distinguish the positive values from the negative ones, but after that on average every second bit only adds more precision to values that are already distinguishable or out of range, but doesn't help with values whose representation has the same prefix. I don't know how to make that airtight, though...