Hacker News Reader

Comment by ClayFerguson | Hacker News Reader

There are many times in software development where you have an array of bits. By definition, an array doesn't have anything "in front" of it. Implementing an array of bits in a computer is a different matter. Normally you store bytes (8 bits at a time), but that's just an implementation detail, and only because computers handle bytes as the fundamental unit. Each two contiguous bits in a bit array can be used to "pick a quadrant" to zoom into a square, recursively. There is no limit or definition of how long the array needs to be unless you want to pre-specify that. You are basically confusing the concepts "Bit Array" with "Two's Compliment Integer storage". These two things are completely separate concepts of storage.

View on HN

But the point of the representation is that locations can easily and unambiguously be stored in a single number, say a 64bit integer. A bit array necessarily has some overhead to specify the number of bits; something unnecessary in this proposal. Yes a standard using two bits per sector and specifying how many bits have been used in the actual representation is easier for a human to start to decipher, but it requires more information to be unambiguous and doesn't have as nice a binary representation (I'd rather have a fixed sized larger representation that the more complex one needed for an arbitrary sized bit array).

I was talking about pure arrays of bits, as a theoretical construct, but you are right to notice that if not all your arrays are the same length, then each array needs to specify a length. 64-bit integers are like bit-arrays where each array is pre-defined to be 64-bits long and therefore doesn't need to store its length. You could define all your bit arrays to be 8 bytes long each and accomplish the same thing. Your better tact at shooting holes in the bit-array approach is not from memory consumption (you loose on those grounds), but you from a 'performance' standpoint, you can make the case the integer comparisons all take one clock cycle, and operations on bit-arrays are slower, because you have to check each bit individually to do logic. Summary: For storage size, bit-arrays win, and for performance integers win. So based on system needs you'd choose a solution, weighing the pros/cons.

Reply on news.ycombinator.com