Bitstring manipulation

The containers package contains IntMap and IntSet types which use some bit fiddling tricks to achieve very high performance.

For example -x `xor` x. This bit fiddling trick is especially magical because it negates an unsigned value. It would be much nicer to express the meaning of this operation in a more natural way.

One possibility I could think of would be a regex-inspired of pattern matching mechanism which could look like this:

.*10{n} -> 1*0{n+1}

This syntax is supposed to mean: "Check if the input ends in a one followed by a number n zeroes, if so produce a bitstring with all ones of the left and n+1 zeroes.

I think this is much easier to understand than the original which uses xor, but it doesn't quite feel perfect yet.

What do you think? Would you use this if it compiled to code that is as fast as the -x `xor` x? Do you have suggestions for improvement?

treeowl,

I think your version is arguably even more confusing, though I certainly wish we had something clearer. If you can suggest something clearer and equally fast available using extant primitives/instructions, I'm all ears and will happily make the change.

jaror,
jaror avatar

I guess you could express it more Haskelly like:

padL 64 1 (cons 1 (takeWhileR (== 0) x))

(if we consider bitstrings to be Seq Bit and I hope that padL speaks for itself)

Would that be less confusing? Or can you try to explain what you find confusing?

romes,

I like the discussion, but I'm not sold on the solution :).

In particular, the {n+1} bit is not immediatly clear to me, it seems like the number of original number of bits is increasing hah!

jaror,
jaror avatar

Good point. I was thinking of transformation that preserve the length of the bitstring like if you're dealing with a type like Word64. Otherwise perhaps you could be more specific about it like this:

.{m}10{n} -> 1{m}0{n+1}
  • All
  • Subscribed
  • Moderated
  • Favorites
  • •
  • haskell
  • ethstaker
  • DreamBathrooms
  • normalnudes
  • magazineikmin
  • InstantRegret
  • GTA5RPClips
  • thenastyranch
  • Youngstown
  • rosin
  • slotface
  • osvaldo12
  • ngwrru68w68
  • kavyap
  • everett
  • megavids
  • Durango
  • Leos
  • cubers
  • mdbf
  • khanakhh
  • tester
  • modclub
  • cisconetworking
  • anitta
  • tacticalgear
  • provamag3
  • JUstTest
  • lostlight
  • All magazines
    •