CODEWITHSUNDEEP
c++algorithmbit-manipulation
newbRaymond
newbRaymond

Reputation: 25

Is there a non-iterative method of toggling groups of bits on and off using a mask?

Suppose I've two bit strings: runs and toggler, where a run is a group of contiguous like bits. Both of these bit strings can have an arbitrary arrangement of 1s and 0s (on and off respectively). For the sake of the question, I will use the example values below:

runs   : 1111011010100011
toggler: 1010001010010110

Does there exist a way to mask the two bit strings, or otherwise utilise any features of c++ outside of iteration (though the more general / language-independent, the better), to produce a result bit string that contains every run of 1s in runs which possesses at least one bit who has a corresponding 1 in toggler? A worked example of this using the example values provided can be seen as follows:

runs   : 1111011010100011
toggler: 1010001010010110
result : 1111011010000011

Where the first, second, third, and fourth runs of 1s in runs all possess at least one 1 corresponding to their constituent bits in toggler.

So far, I have that it is apparent that the positions of some of result's 0s can be identified, being the bits corresponding to ~runs. It is also apparent that the positions of some of result's 1s can be identified as runs & toggler. Given this information, any remaining unknown bits (equivalent to the bits that satisfy the condition runs & ~toggler) can be determined to be 0 iff the bits at either end of that run of unknown bits are zero. This can once again be seen below in the bit string unknown:

runs   : 1111011010100011
toggler: 1010001010010110
unknown: 1_1_0_1010_0001_ // 1 = runs & toggler, 0 = ~runs, _(unknown) = runs & ~toggler
result : 1111011010000011

Upvotes: 0

Views: 76

Answers (1)

user555045
user555045

Reputation: 64904

It seems possible, but packed with annoying edge cases and some operations that aren't exactly "nice" even though they technically avoid iteration.

First the nice part. Getting, for each "group", a bit indicating whether any toggle was turned on for that group. An approach could be: take the toggles, put in a "blocker" 1 in the bit just after a group, and subtract the starting point of every group. Then if no toggle was set in a group, the "blocker" is reset by the borrow. Otherwise, if there is a toggle set, that toggle bit "eats" the borrow and the blocker survives. In code:

runs_first = runs & ~(runs << 1);
runs_after = ~runs & (runs << 1);
toggles_blocked = toggles | runs_after;
selected_groups = runs_after & (toggles_blocked - runs_first);

Example with your numbers (with zero pre-pended, to avoid an unfortunate edge case):

runs           : 01111011010100011
toggles        : 01010001010010110
runs_first     : 00001001010100001
runs_after     : 10000100101000100
toggles_blocked: 11010101111010110
difference     : 11001100100110101
selected_groups: 10000100100000100

If the groups were fixed-length, it would now be easy to expand those single-bit-flags to whole-group-masks.. or if the bit was located at the start of the group, it would also be easy. Reversing the bits gives a solution, using a subtraction trick:

rev_selected = reverse(selected_groups >> 1);
rev_runs = reverse(runs);
rev_runs_after = ~rev_runs & (rev_runs << 1);
rev_groupmask = (rev_runs_after - rev_selected) & rev_runs;
groupmask = reverse(rev_groupmask)

But even an "efficient reverse" isn't that efficient, unless there is direct hardware support for it (eg rbit on ARM, grevi on RISC-V with extension B).

Upvotes: 2

Related Questions