81

I'm currently in the process of writing a tree enumerator where I've come across the following problem:

I'm looking at masked bitsets, i.e. bitsets where the set bits are a subset of a mask, i.e. 0000101 with mask 1010101. What I want to accomplish is increment the bitset, but only with respect to the masked bits. In this example, the result would be 0010000. To make it a bit clearer, extract only the masked bits, i.e. 0011, increment them to 0100 and distribute them to the mask bits again, giving 0010000.

Does anybody see an efficient way to do this, short of implementing the operation by hand using a combination of bitscans and prefix masks?

gsamaras
  • 71,951
  • 46
  • 188
  • 305
Tobias Ribizel
  • 5,331
  • 1
  • 18
  • 33

3 Answers3

124

Just fill the non mask bits with ones so that they propagate carry:

// increments x on bits belonging to mask
x = ((x | ~mask) + 1) & mask;
zch
  • 14,931
  • 2
  • 41
  • 49
  • 11
    That's a nice trick...Almost the magic I said there is none :) – Eugene Sh. Jun 26 '17 at 19:26
  • 8
    @EugeneSh. Never believe it's not so. – zch Jun 26 '17 at 20:01
  • 24
    Presumably not important to OP since they accepted, but it perhaps should be noted that this will zero the non-mask bits. If they _were_ needed elsewhere, you'd have to be more careful replacing `x`. Possibly `x = (x & ~mask) | (((x | ~mask) + 1) & mask);`. – TripeHound Jun 27 '17 at 10:11
  • 2
    @TripeHound If they weren't needed, what would be the point of even using a bit mask? – someonewithpc Jun 28 '17 at 00:02
  • 1
    @someonewithpc Not sure what you're trying to say/ask. I don't know _why_ the OP needs to increment a non-adjacent set of bits, so I don't know whether the _other_ bits in the original value matter or not. E.g. if the original value were `0101101` (e.g. `.1.1.0.` in the non-mask bits and `0.0.1.1` in the "counter") would they _need_ `0111000` (a new "counter" of `0.1.0.0` while preserving `.1.1.0.`) or is just `0010000` acceptable. This answer (and probably others, though I've not checked) give the latter; my version should give the former if that is what's required. – TripeHound Jun 28 '17 at 06:54
21

While not intuitive compared to the accepted answer, this works in only 3 steps:

x = -(x ^ mask) & mask;

This can be verified as suggested by zch:

  -(x ^ mask)
= ~(x ^ mask) + 1  // assuming 2's complement
= (x ^ ~mask) + 1
= (x | ~mask) + 1  // since x and ~mask have disjoint set bits

Then it becomes equivalent to the accepted answer.

nglee
  • 1,913
  • 9
  • 32
  • 2
    The answer by zch is very intuitive, I can immediately see it is right because of his clear explanation. What is the logic of this answer? How does this formula work out to give the desired effect? I am curious about the process of discovery, the nature of the insight here. – FooF Jun 27 '17 at 05:17
  • I think your verification would be much simpler if you just proved that `-(x ^ mask) == (x | ~mask) + 1` whenever x is a subset of mask and then referred to my answer. – zch Jun 27 '17 at 09:46
  • 5
    `-(x^mask) == ~((x ^ mask) - 1) == ~(x ^ mask) + 1 == (x ^ ~mask) + 1 == (x | ~mask) + 1`. Last equation holds because bitsets are disjoint, others are always true (at least in 2-complement). – zch Jun 27 '17 at 09:51
  • 1
    Those who are curious about the steps I took to derive this answer can refer to [this page](https://nleeshong.wordpress.com/2017/06/28/bit-manipulation-1/). – nglee Jun 27 '17 at 16:27
  • 5
    Maybe worth pointing out that these don't optimize the same, which is often relevant to people doing bit-twiddling: https://godbolt.org/g/7VWXas - although which one is actually shorter seems to depend on the compiler. No idea which one would be *faster* or if the difference is significant. – Alex Celeste Jun 27 '17 at 20:04
8

If the order of iteration is not that important, and a decrement operation will satisfy your needs, it is possible to use only two operations:

Let's start with

x = mask

and get previous value with

x = (x - 1) & mask

x - 1 part changes the last non-zero bit to zero, and sets all less significant bits to 1's. Then & mask part leaves only mask bits among them.

DAle
  • 8,990
  • 2
  • 26
  • 45
  • 2 ops, nice. I'd argue however that it is the same approach, only propagating borrow through zeros, rather than carry through ones. – zch Jun 27 '17 at 22:03
  • @zch, that's right, thanks. I'll rephrase the answer – DAle Jun 28 '17 at 06:50
  • only works if x starts with all the non-mask bits clear. – Jasen Jun 28 '17 at 10:48
  • @Jasen, sure. But it's not difficult to set those non-mask bits. And other answers have the similar issue. – DAle Jun 28 '17 at 18:18