How many ways can I replace the 0 in a string?

We say that integer A conforms to integer B if, in all positions where B has bits set to 1, A has corresponding bits set to 1. For example:

00 0000 1111 0111 1101 1110 0000 1111(BIN) = 16,244,239 conforms to
00 0000 1100 0110 1101 1110 0000 0001(BIN) = 13,032,961, but
11 0000 1101 0111 0000 1010 0000 0101(BIN) = 819,399,173 does not conform to
00 0000 1001 0110 0011 0011 0000 1111(BIN) = 9,843,471.

that, given three unsigned 30-bit integers A, B and C, returns the number of unsigned 30-bit integers conforming to at least one of the given integers.

For example, for integers:

A = 11 1111 1111 1111 1111 1111 1001 1111(BIN) = 1,073,741,727,
B = 11 1111 1111 1111 1111 1111 0011 1111(BIN) = 1,073,741,631, and
C = 11 1111 1111 1111 1111 1111 0110 1111(BIN) = 1,073,741,679,

the function should return 8, since there are 8 unsigned 30-bit integers conforming to A, B or C, namely:

11 1111 1111 1111 1111 1111 0011 1111(BIN) = 1,073,741,631,
11 1111 1111 1111 1111 1111 0110 1111(BIN) = 1,073,741,679,
11 1111 1111 1111 1111 1111 0111 1111(BIN) = 1,073,741,695,
11 1111 1111 1111 1111 1111 1001 1111(BIN) = 1,073,741,727,
11 1111 1111 1111 1111 1111 1011 1111(BIN) = 1,073,741,759,
11 1111 1111 1111 1111 1111 1101 1111(BIN) = 1,073,741,791,
11 1111 1111 1111 1111 1111 1110 1111(BIN) = 1,073,741,807,
11 1111 1111 1111 1111 1111 1111 1111(BIN) = 1,073,741,823.

Goal

def solution(A,B,C):
   ...
   return number_of_compinations

Solution 1:

Here is a function that works for 3 numbers:

def zero_count(n,k):
    return bin(n)[2:].zfill(k).count('0')

def count_extensions(a,b,c,k):
    #include individual items
    s = 2**zero_count(a,k)
    s += 2**zero_count(b,k)
    s += 2**zero_count(c,k)

    #exclude pairs
    s -= 2**zero_count(a|b,k)
    s -= 2**zero_count(a|c,k)
    s -= 2**zero_count(b|c,k)

    #include all 3:
    s += 2**zero_count(a|b|c,k)
    return s

a = 1073741727
b = 1073741631
c = 1073741679

print(count_extensions(a,b,c,30)) #8

It uses the 3-set inclusion-exclusion principle. The full principle would be required if you want to generalize to more than 3 numbers.