Count bitmasks, list 0s

Question

I had the following question in an interview, and I suppose I gave a working implementation, but I was wondering if there was a better implementation that was faster, or just a trick I missed.

Given 3 unsigned 30-bit integers, return the number of 30-bit integers that, compared to any of the source numbers, have the same position bits set to 1. This we list all 0s

Let me give you an example, but for clarity, let's use 4bit.

Given:

A = 1001 B = 0011 C = 0110 

It should return 8, since there are 8 4-bit ints in the set. Set:

 0011 0110 0111 1001 1011 1101 1110 1111 

Now, as I worked, I needed to take each number and list a lot of possibilities, and then count all the individual values. As I enumerated the set, to start with the number, add it to it, and then OR take it with me until I get to the mask. With the number itself in the set and the mask (all set to 1) also in the set. For example, to list a set of 1001:

 1001 = the start 1011 = (1001 + 1) | 1001 1101 = (1011 + 1) | 1001 1111 = (1101 + 1) | 1001 (this is the last value as we have reached our mask) 

So do this for each number, and then count uniques.

This is it in python code (but the language does not matter as long as you can perform bitwise operations, so why this question is flagged for c / C ++):

 MASK = 0x3FFFFFFF def count_anded_bitmasks( A, B, C ): andSets = set( enumerate_all_subsets(A) + enumerate_all_subsets(B) + enumerate_all_subsets(C) ) return len(andSets) def enumerate_all_subsets( d ): andSet = [] n = d while n != MASK: andSet.append(n) n = (n + 1) | d andSet.append(n) return andSet 

Now it works and gives the correct answer, but I wonder if I missed the trick. Since the question was to ask the score and not list all the values, perhaps there is a much faster way. Either by combining the numbers first, or by getting an invoice without transfer. I have a feeling. Since numbers containing many zeros, the enumeration grows exponentially, and this can take quite a while.

If you have AB and C, count a set of numbers with bits set to 1, where A or B or C have corresponding bits set to 1.

Some people do not understand the question (they did not help, so I did not ask it correctly, the first of them). Let us use the above values ​​of AB and C:

A:

 1001 1011 1101 1111 

IN:

 0011 0111 1011 1111 

FROM

 0110 0111 1110 1111 

Now combine these sets and count the individual records. This is the answer. Is there a way to do this without listing the values?

Edit: Sorry for the error. Fixed.

Answer 1

 N = 4 def supers(number): zeros = sum(1 for bit in xrange(N) if (number >> bit) & 1 == 0) return 2**zeros def solve(a,b,c): total = supers(a) + supers(b) + supers(c) total -= supers(a | b) # counted twice, remove one total -= supers(b | c) # counted twice, remove one total -= supers(a | c) # counted twice, remove one total += supers(a | b | c) # counted three times, removed three times, add one return total print solve(0b1001,0b0011,0b0110) 

Description

Let S(n) be the product given by n .

supers(n) returns |S(n)| set size for n. supers not a very good name, but I am having problems with the best

The trick is to understand that S(a) ^ S(b) = S(a | b) . As a result, using supers, I can determine the size of all these sets.

To find out the rest, draw a Venn diagram of the sets.

Answer 2

EDIT: updated requirement: given three unsigned 30-bit integers, return the number of 30-bit integers that, compared to any of the source numbers, have the same position bits set to 1. This we list all 0s

OK, a little harder. It is easy to calculate for a single number, since in this case the number of possible integers depends only on the number of zero bits, for example:

 // Count bits not set const size_t NUMBITS=30; size_t c; size_t v = num; for (c=NUMBITS; v; v >>= 1) c -= v & 1; return c; 

You could naively try to expand this to three integers by doing it for each and summing up the results, however this would be wrong because the possibilities must be unique, for example. given

 A = 1001 B = 0011 C = 0110 

You think, for example. 1111 three times, not once. You must subtract the number of combinations that are divided between any two numbers, but do not subtract any combination twice. This is just a translation of Winston Evert's answer in C ++!

 size_t zeroperms(size_t v) { // Count number of 0 bits size_t c = 1; for (c=NUMBITS; v; v >>= 1) c -= v & 1; // Return number of permutations possible with those bits return 1 << c; } size_t enumerate(size_t a, size_t b, size_t c) { size_t total = zeroperms(a) + zeroperms(b) + zeroperms(c); total -= zeroperms(a | b); // counted twice, remove one total -= zeroperms(b | c); // counted twice, remove one total -= zeroperms(a | c); // counted twice, remove one total += zeroperms(a | b | c); // counted three times, removed three times, add one return total; } 

Answer 3

Trick 1:

The general answer is to combine every single 30-bit number. This results in a bitwise OR join operator. This means that we can do D = A | B | C D = A | B | C D = A | B | C With your 4-bit example we come to D = 1111 Now we need to work with only 1 number

Trick 2:

A little math tells us that for every 1 we double our possible set of numbers. This means that all you have to do is raise 2 to 1 sec. Count 1 with a loop, going down each time

 bits = 0 D = 0b1111 #our number from trick 1 for i in range(4): #here 4 is the number of bits if D & 1: bits += 1 D >>= 1 #drop off the smallest number print 2 ** bits 

in this case he will print 16