[HN Gopher] Popcount walks: next, previous, toward and nearest
___________________________________________________________________
Popcount walks: next, previous, toward and nearest
Author : ingve
Score : 37 points
Date : 2023-11-13 13:03 UTC (1 days ago)
(HTM) web link (marc-b-reynolds.github.io)
(TXT) w3m dump (marc-b-reynolds.github.io)
| SomeRndName11 wrote:
| What kind of UB the author is talikng about?
| Strilanc wrote:
| 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 wrote:
| 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)
| Karellen wrote:
| > C++ should clearly have picked Unspecified Behaviour
| rather than Undefined Behaviour but too late now.
|
| Why is it too late? Changing it in a later version of the
| standard wouldn't be a further constraint on any written
| code; any code which is currently correct will remain
| correct, and some code which could have done literally
| anything will now only be able to have one of a few
| possible behaviours.
| akoboldfrying wrote:
| I suppose it would break any currently compliant C++
| compiler for which the target platform's CPU will throw
| an exception (or even less likely, return a random
| number) when shifting by a full word.
|
| But I'd also suppose there aren't many such CPUs. Does
| anyone know of any?
| protomolecule wrote:
| "C++ should clearly have picked Unspecified Behaviour
| rather than Undefined Behaviour but too late now"
|
| It's never too late to replace Undefined Behaviour with
| Unspecified Behaviour.
| nalzok wrote:
| > 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?
| Strilanc wrote:
| 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
| bicsi wrote:
| 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 wrote:
| This could be useful for combinatorial tasks such as iterating
| over all the ways to draw k items without replacement from a bag
| containing n distinct items. You start out with 1<<k - 1 (which
| has its k low-order bits set to 1) and keep going up to the next
| higher integer with the same popcount until bit n is set to 1, at
| which point you stop.
| akoboldfrying wrote:
| 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
___________________________________________________________________
(page generated 2023-11-14 23:01 UTC)