[wjmao88]

So I don't really understand this after reading the explanations.

1. You claim to have explained the height of the sticks "later". Maybe you had it explained in one of the paragraphs, but I just don't see it.

2. In the diagram that is supposed to illustrate the left sweeping part, it has fancy windows and doors but doesn't have anything to explain why the lines are drawn that way. The home page animation also didn't give me any insight on how that part is supposed to work.

[cormacrelf]

Stack height just visualises the repeated transition function for "next spot to jump to". You don't have to compute the stick heights and do searches, just execute p <- (p | (p + 1)) & MASK for a "right horizontal line". This transition is more simply explained as "set the least significant 0 bit". The important thing is that each successive jump is at least double the size of the previous one, which intuitively gives you the log2 in the worst case complexity. There is a paragraph on right skipping, but not left skipping.

For left skipping AKA "gather", what you're trying to do is log-skip across contiguous zeroes in the auxiliary array. So you skip bigger and bigger regions until you hit a nonzero spot. I'd have to think a bit more to prove that you do actually hit the next number, but the visualisation of the transitions should get you in the ballpark: the tall sticks tend to get numbers written under them by the lesser sticks to their left, and when you are skipping from the right, you tend to hit the tall sticks.

The explanation doesn't mention it, but the left-skips are defined as p <- (((p+1) & p) - 1) & MASK. This is also simply explained: "clear any contiguous 1s pinned to the least significant end, then subtract 1 to create more 1s" e.g.:

    1100 1100 (      =204)
    1100 1011 (-1,   =203)
    1100 0111 (-4,   =199)
    1011 1111 (-8,   =191)
    0111 1111 (-64,  =127)
    1111 1111 (-128, =255, wrapped)

So the "buildings" get wider as you go, until you hit another nonzero spot, and you start drawing thin buildings again because you start from the element to its left, whose binary representation ends with 11*0.

The bitwise ops are the key to understanding why you can draw the sticks at those heights: for each index i, simply draw to height = 1 + the # of trailing 1s in i. Many trailing ones makes for bigger jumps in either direction. So the wide buildings are also tall.

[daniel-cussen]

Thanks so much for this great, novel explanation.

[cormacrelf]

You have my permission to use it if you like!