Suppose I have some binary mask `mask`

. (e.g. 0b101011011101)

Is there an efficient method of computing all integers `k`

such that `k & mask == k`

? (where `&`

is the bitwise AND operator) (alternatively, k & ~mask == 0)

If `mask`

has `m`

ones, then there are exactly 2^{m} numbers that satisfy this property, so it seems like there should be some kind of process that is O(2^{m}). Enumerating the integers less than the mask is wasteful (though easy to eliminate values that do not apply).

# Best How To :

I figured it out... you can identify all the single bit patterns like as follows, since the least significant 1 bit of any integer `k`

is cleared when calculating `k & (k-1)`

:

```
def onebits(x):
while x > 0:
# find least significant 1 bit
xprev = x
x &= x-1
yield x ^ xprev
```

and then I can use the ruler function to XOR in various combinations of 1 bits to emulate which bits of a counter are toggled each time:

```
def maskcount(mask):
maskbits = []
m = 0
for ls1 in onebits(mask):
m ^= ls1
maskbits.append(m)
# ruler function modified from
# http://lua-users.org/wiki/LuaCoroutinesVersusPythonGenerators
def ruler(k):
for i in range(k):
yield i
for x in ruler(i): yield x
x = 0
yield x
for k in ruler(len(maskbits)):
x ^= maskbits[k]
yield x
```

which looks like this:

```
>>> for x in maskcount(0xc05):
... print format(x, '#016b')
0b00000000000000
0b00000000000001
0b00000000000100
0b00000000000101
0b00010000000000
0b00010000000001
0b00010000000100
0b00010000000101
0b00100000000000
0b00100000000001
0b00100000000100
0b00100000000101
0b00110000000000
0b00110000000001
0b00110000000100
0b00110000000101
```