Fast way to find a intersection between two sets of numbers, one defined by a bitwise condition and another by an arithmetic condition

Question

This is probably well covered ground, but I'm ignorant on the subject so I'll be using amateurish terminology. Let's say I'm messing around with some set of conditions that each define a non-zero set of numbers within an int, let's just say 8-bit int. So for a bitwise one, I may have this: ``` 11XX00XX ``` Saying that I want all bytes that have 1s where there are 1s, 0s where there are 0s, and don't care about the Xs. So 11110000 or 11000010 fulfills this, but 01110000 does not. Easy enough, right? For arithmetic conditions, I can only imagine there being some use of ==, !=, >=, >, <=, or < with comparison with a constant number. So I may say: ``` X > 16 ``` So any number greater than 16 (00010000). What if I want to find all numbers that are in both of those above example sets? I can tell by looking at it that any numbers ending in 100XX will fit the requirements, so the bitwise part of the interseection includes 11X100XX. Then I have to include the region 111X00XX to fill the rest o…

Accepted Answer

Extending a bit on saluce's answer:

Bit testing

You can build test patterns, so you don't need to check each bit individually (testing the whole number is faster than testing one-bit-a-time, especially that the on-bit-a-time test the whole number just as well):

```
testOnes = 128 & 64 // the bits we want to be 1
testZeros = ~(8 & 4) // the bits we want to be 0, inverted
```

Then perform your test this way:

```
if (!(~(x & testOnes) & testOnes) &&
    !(~(~x | testZeros))) {
  /* match! */
}
```

Logic explained:

First of all, in both `testOnes` and `testZeros` you have the bits-in-interest set to 1, the rest to 0.

```
testOnes testZeros
11000000 11110011
```

Then `x & testOnes` will zero out all bits we don't want to test for being ones (note the difference between `&` and `&&`: `&` performs the logical `AND` operation bitwise, whereas `&&` is the logical `AND` on the whole number).

```
testOnes
11000000
x        x & testOnes
11110000 11000000
11000010 11000000
01010100 01000000
```

Now at most the bits we are testing for being 1 can be 1, but we don't know if all of them are 1s: by inverting the result (`~(x & testOnes)`), we get all numbers we don't care about being 1s and the bits we would like to test are either 0 (if they were 1) or 1 (if they were 0).

```
testOnes
11000000
x        ~(x & testOnes)
11110000 00111111
11000010 00111111
01010100 10111111
```

By bitwise-`AND`-ing it with `testOnes` we get 0 if the bits-in-interest were all 1s in `x`, and non-zero otherwise.

```
testOnes
11000000
x        ~(x & testOnes) & testOnes
11110000 00000000
11000010 00000000
01010100 10000000
```

At this point we have: 0 if all bits we wanted to test for 1 were actually 1s, and non-0 otherwise, so we perform a logical `NOT` to turn the 0 into `true` and the non-0 into `false`.

```
x        !(~(x & testOnes) & testOnes)
11110000 true
11000010 true
01010100 false
```

The test for zero-bits is similar, but we need to use bitwise-`OR` (`|`), instead of bitwise-`AND` (`&`). First, we flip `x`, so the should-be-0 bits become should-be-1, then the `OR`-ing turns all non-interest bits into 1, while keeping the rest; so at this point we have all-1s if the should-be 0 bits in `x` were indeed 0, and non-all-1s, otherwise, so we flip the result again to get 0 in the first case and non-0 in the second. Then we apply logical `NOT` (`!`) to convert the result to `true` (first case) or `false` (second case).

```
testZeros
11110011
x        ~x       ~x | testZeros ~(~x | testZeros) !(~(~x | testZeros))
11110000 00001111 11111111       00000000          true
11000010 00111101 11111111       00000000          true
01010100 10101011 11111011       00000100          false
```

Note: You need to realize that we have performed 4 operations for each test, so 8 total. Depending on the number of bits you want to test, this might still be less than checking each bit individually.

Arithmetic testing

Testing for equality/difference is easy: `XOR` the number with the tested one -- you get 0 if all bits were equal (thus the numbers were equal), non-0 if at least one bit was different (thus the numbers were different). (Applying `NOT` turns the equal test result `true`, differences to `false`.)

To test for unequality, however, you are out of luck most of the time, at least as it applies to logical operations. You are correct that checking for powers-of-2 (e.g. 16 in your question), can be done with logical operations (bitwise-`AND` and test for 0), but for numbers that are not powers-of-2, this is not so easy. As an example, let's test for `x>5`: the pattern is 00000101, so how do you test? The number is greater if it has a 1 in the fist 5 most-significant-bits, but 6 (00000110) is also larger with all first five bits being 0.

The best you could do is test if the number is at least twice as large as the highest power-of-2 in the number (4 for 5 in the above example). If yes, then it is larger than the original; otherwise, it has to be at least as much as the highest power-of-2 in the number, and then perform the same test on the less-significant bits. As you can see, the number of operations are dynamic based on the number of 1 bits in the test number.

Linked bits

Here, `XOR` is your friend: for two bits `XOR` yields 0 if they are the same, and 1 otherwise.

I do not know of a simple way to perform the test, but the following algorithm should help:

Assume you need bits `b1`, ..., `bn` to be the same (all 1s or all 0s), then zero-out all other bits (see logical-`AND` above), then isolate each bit in the test pattern, then line them up at the same position (let's make it the least-significant-bit for convenience). Then `XOR`-ing two of them then `XOR`-ing the third with the result, etc. will yield an even number at every odd step, odd number at every even step if the bits were the same in the original number. You will need to test at every step as testing only the final result can be incorrect for a larger number of linked-…

Fast way to find a intersection between two sets of numbers, one defined by a bitwise condition and another by an arithmetic condition

Solution

Problem