Popcount walks: next, previous, toward and nearest

http://marc-b-reynolds.github.io/math/2023/11/09/PopNextPrev.html

by ingve • 3 years ago

48 20 3 years ago

marc-b-reynolds.github.io

What kind of UB the author is talikng about?

Strilanc4• 3 years ago

If x is n bits long, it's undefined behavior to evaluate x >> n. You can only shift by amounts smaller than the register width. IMO this is one of the more annoying instances of UB. Precisely because of situations like this, where you shift by "number of leading zeroes" which can end up being the width of the register.

tialaramex• 3 years ago

This is one of the classic examples where C++ should clearly have picked Unspecified Behaviour rather than Undefined Behaviour but too late now. Nobody wants UB here, and the set of things CPUs actually might provide is enumerable.

Maybe I should suggest avoiding the same fate for Rust's unchecked_shl and unchecked_shr. (These aren't stabilized yet unlike the safe options and the rotates)

nalzok• 3 years ago

How does that work? I don't really know, I pulled this out of the void with a SAT solver. Basically magic.

That's pretty cool. How do you ask an SAT solver for "the nearest integer with the same population count", and how do you describe the available bitwise operations to it?

lifthrasiir• 3 years ago

It would be more like an SAT-guided program synthesis---you can exhaustively generate all functions with at most n operations, and you can describe that particular operation as a boolean formula, so you can feed all of them to filter ones that are provably equivalent.

As for the actual boolean formula, I believe that he used his own creation, Haroldbot [1] which can evaluate bitwise expressions and enumerate all cases where the expression evaluates to true. Since simple formulas for previous and next integer with the same popcount, it should be doable. I've even constructed a concrete formula with the suggested formula:

    let n = (let t = x + (x & -x) in let u = x & ~t in t ^ ((u >>s tzcnt(u)) >>s 1)) in
    let p = (let v = x - (~x & (x + 1)) in let w = ~x & v in v ^ ((w >>s tzcnt(w)) >>s 1)) in
    let c = (let y = -x & (x + 1) in x ^ y ^ (y >> 1)) in
    (n == -1) || (p == 0) || (
        (p < x) && (popcnt(p) == popcnt(x)) &&
        (x < n) && (popcnt(x) == popcnt(n)) &&
        ((x - p > n - x) && (c == n)) || ((x - p <= n - x) && (c == p)))
    )

...where `n` is for the next such integer (or all 1s), `p` is for the previous such integer (or all 0s), `c` is for the closest such integer, and assuming that both `p` and `n` exists, `c` should be the closest of either `p` or `n`. This expression can be mechanically translated to a single boolean formula, which Haroldbot internally does for complicated formulas [2].

[1] http://haroldbot.nl/

[2] It apparently uses binary decision diagrams for simpler cases: http://haroldbot.nl/how.html

Strilanc4• 3 years ago

I like these kinds of bit twiddling puzzles.

One that I recently did was for iterating over possible errors of weight w in a quantum stabilizer code (for [1]). In a classical code this would just be the problem in the blog post, since there's only one type of error (bit flips). In a quantum code you have bit flips (X) but also phase flips (Z) and combination-bit-and-phase-flips (Y) all having weight 1. So the problem becomes: given ints (x, z) find the next (x2, z2) such that popcnt(x2 | z2) == popcnt(x | z).

The solution I came up with, which is likely very suboptimal, was to iterate over single-integer solutions for a given weight. Then, for each single-integer solution m, iterate over the pairs x,z where x|z == m. Here's python pseudocode for the second part:

    def pair_sat_increment(x: int, z: int, m: int) -> Tuple[int, int]:
        """Returns the next (x, z) such that x | z == m."""
        inc = x & z
        up = ~inc
        inc |= ~m
        inc += 1
        inc &= m
        up &= inc
        z &= inc | ~x
        z ^= x & up
        x ^= up
        return x, z

[1]: https://github.com/quantumlib/Stim/issues/397

pbsd2• 3 years ago

A simple way to do the latter is

  for(u64 x = -m & m; ;x = (x - m) & m) {
    const u64 r = x ^ m;
    for(u64 t = -x & x; ; t = (t - x) & x) {
      const u64 z = r | t;
      // Use (x,z)
      if(t == 0) break;
    }
    if(x==0) break;
  }

Strilanc4• 3 years ago

Nice. You need to initialize x to 0 instead of -m&m though, or you miss the solution with x=0.

bicsi• 3 years ago

As a competitive programmer, I’ve seen similar ‘magic’ tricks (including this one) here: https://github.com/kth-competitive-programming/kactl/blob/ma... (page 23, 10.5.1)

bumbledraven• 3 years ago

This could be useful for combinatorial tasks such as iterating over all the ways to draw 𝑘 items without replacement from a bag containing 𝑛 distinct items. You start out with 1<<𝑘 – 1 (which has its 𝑘 low-order bits set to 1) and keep going up to the next higher integer with the same popcount until bit 𝑛 is set to 1, at which point you stop.

akoboldfrying2• 3 years ago

Interesting! I didn't initially click to the fact that Harold's snippet was solving a different problem than the one previously talked about, so was confused why it would "get stuck" flicking between two states after shrinking the rightmost run (of 1s or 0s), but that is indeed the desired behaviour if you want the nearest (not the next or previous) integer.

I actually found the author's complementing trick for getting the previous integer more interesting (because more applications):

However since we already have a version that walks to the next we can simply apply a linear transform to map/unmap the input/result. The ones complement (~x) reverses the notion of unsigned integer ordering so the follow function walks to the previous

Popcount walks: next, previous, toward and nearest

Related Stories