3 ms·

It also did a step by step breakdown, but here's what GPT-4o summarized the function as: What does the code achieve? This function essentially extracts and co

It also did a step by step breakdown, but here's what GPT-4o summarized the function as: What does the code achieve? This function essentially extracts and compacts the bits from x that correspond to the 1 bits in the mask m. It does so by successively shifting the extracted bits towards the least significant positions, while keeping the relative order of the bits intact. The algorithm is likely inspired by techniques used in bit packing or bit extraction, where the goal is to gather specific bits from a number based on a mask and pack them together efficiently.

atomic128 2y ago
Right, so it's trained on this text, from the BUGFIX-66 page where that code appears: Bug 47: Bit Extraction Misguided By Mask This is Guy L. Steele Jr.'s parallel suffix algorithm for bit extraction (U.S. Patent 6715066). Bits of x that correspond to 1-bits in m are shifted low and made consecutive, preserving relative order. The method masks x with m to isolate such bits and then repeatedly shifts 1- bits of x low by powers of two. A 1-bit in x with n less significant 0-bits in m is shifted low by a series of powers of two that sum to n. And it's trained on the patent, too. But there's something very clever happening in the repeated prefix sums of the holes, and that's the magic that makes it work. Does it understand how repetition of this works to achieve the extraction? odd := holes odd ^= odd << 1 odd ^= odd << 2 odd ^= odd << 4 odd ^= odd << 8 odd ^= odd << 16 odd ^= odd << 32 holes &^= odd What's happening to holes when this piece of code is repeated over and over? Does it really understand the algorithm (i.e., the magic of the code sequence above) or is it just recognizing the "bit extraction code" from its training data, and executing it like a machine? That's my question.

atomic128 2y ago

Right, so it's trained on this text, from the BUGFIX-66 page where that code appears: Bug 47: Bit Extraction Misguided By Mask This is Guy L. Steele Jr.'s parallel suffix algorithm for bit extraction (U.S. Patent 6715066). Bits of x that correspond to 1-bits in m are shifted low and made consecutive, preserving relative order. The method masks x with m to isolate such bits and then repeatedly shifts 1- bits of x low by powers of two. A 1-bit in x with n less significant 0-bits in m is shifted low by a series of powers of two that sum to n. And it's trained on the patent, too. But there's something very clever happening in the repeated prefix sums of the holes, and that's the magic that makes it work. Does it understand how repetition of this works to achieve the extraction? odd := holes odd ^= odd << 1 odd ^= odd << 2 odd ^= odd << 4 odd ^= odd << 8 odd ^= odd << 16 odd ^= odd << 32 holes &^= odd What's happening to holes when this piece of code is repeated over and over? Does it really understand the algorithm (i.e., the magic of the code sequence above) or is it just recognizing the "bit extraction code" from its training data, and executing it like a machine? That's my question.