Hacker News Reader

Comment by ClayFerguson | Hacker News Reader

If you take a square, and split into 4, that has 2-Bit indexes. If your square has been split twice, it has 4-bit indexes for each of the tiniest sub-squares. So 'granularity' is a function of 'number of splits'. Quadrant a=00, b=01, c=10, d=11. So a bit sequence like 0110, would mean subquadrant 'c', within subquadrant 'b'. Each additional pair of bits added onto the right side "zooms you in" deeper by choosing which quadrant to jump to within a given square. Each time you zoom in, that requires two additional bits. Upper right hand corner would be an infinite series of 01010101010101 repeating. Top right quad of top right quad of top right quad, etc.

View on HN

But most of the time these numbers will be represented in fixed size integers (64 bit words for example); there is no easy way to represent the bit sequence 0110 without making it at least 00000110, but more likely 64 bits, which becomes ambiguous; is this the top left of the top left of the top left of the top right of the bottom right (or whatever those coordinated might represent)? Or do we only look at the last two pairs? how many bits are significant? When sequential integers are used as described, there's no ambiguity; you can always figure out what where a value's quad is positioned from its magnitude.

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.

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