EABitTricks.h - Hackdot

Re:EABitTricks.h by danbruc on Monday December 19, 2022 @05:21PM (#34058583)

And here is the fixed version, I hope.

  zeroOneEdges         = x & (x ^ (x >> 1)) // This must be a signed arithmetic shift.
  rightmostZeroOneEdge = zeroOneEdges & -zeroOneEdges
  toggleMask           = rightmostZeroOneEdge | (rightmostZeroOneEdge << 1)
   
  rightmostOne = x & -x
  shiftMask    = rightmostZeroOneEdge - 1;
  onesToShift  = x & shiftMask
  shiftedOnes  = onesToShift / rightmostOne // This must be an unsigned division.
  
  x = ((x & ~shiftMask) ^ toggleMask) | shiftedOnes

Now it wraps around without a conditional expression but just as the one from the library will divide by zero if called with zero, so either do not do this or add a check for zero and return zero in that case. It works for all ones.

My first attempt was on the right track but also missing a step. Not only must the rightmost 01 edge be turned into 10 but also all the ones to the right of the 01 edge must be shifted back to the right, i.e. <rest>01<ones><zeros> must become <rest>10<zeros><ones>. This shift is done with division and it is important that it is an unsigned division. It is also important that the 01 edge detection shift is a signed arithmetic shift.

The algorithm from the library and my solution are quite similar and they might actually be identical with the one from the library being more optimized and shorter. I would not be surprised if the one from the library actually also works in principle but the implementation got a tiny detail about the signedness of one of the operations wrong, because that will result in the described issues, i.e. not working properly once the sign bit gets involved, either for all ones or during the wrap around.

[ Parent | on HN ]

Re:EABitTricks.h by anonymoushn on Monday December 19, 2022 @08:33PM (#34060397)

Super cool, I'll have to have closer look sometime. To handle zero, if you have ctz, you can replace the divide with two bitwise shifts. This may sometimes be faster than the divide even if you don't have ctz.

[ Parent | on HN ]

Re:EABitTricks.h by danbruc on Tuesday December 20, 2022 @03:19AM (#34063083)

Two shifts? I think ctz plus a single shift should do.

  shiftedOnes = (x & (rightmostZeroOneEdge - 1)) >> ctz(x) // This must be a logical shift.

With all the fancy bit level instruction, this could probably be simplified in general, but I usually avoid them because I mostly see this as an exercise in making it work if you only have access to the basic arithmetic and logic operations and shifts.

[ Parent | on HN ]

Re:EABitTricks.h by anonymoushn on Tuesday December 20, 2022 @02:54PM (#34071536)

You need two shifts in C++ because shifting a uint32_t by 32 is UB. Every actual computer probably gives you 0 if you shift 0 right by a too-large amount though...

[ Parent | on HN ]

Re:EABitTricks.h by danbruc on Wednesday December 21, 2022 @05:50AM (#34079017)

Fortunately my encounters with C and C++ have been rare and brief.

[ Parent | on HN ]