Databases
StackOverflow2013
Postsdbo
POCount bitmasks, enumerate 0s
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POCount bitmasks, enumerate 0s
    primarykey
    data
    text
    <p>I had the following question in an interview and I believe I gave a working implementation but I was wondering if there was a better implementation that was quicker, or just a trick I missed.</p> <p>Given 3 unsigned 30-bit integers, return the number of 30-bit integers that when compared with any of the original numbers have the same position bits set to 1. That is we enumerate all the 0s</p> <p>Let me give an example, but lets use 4bit for clarity.</p> <p>Given:</p> <pre><code>A = 1001 B = 0011 C = 0110 </code></pre> <p>It should return 8 since there are 8 4bit ints that are in the set. The set being:</p> <pre><code>0011 0110 0111 1001 1011 1101 1110 1111 </code></pre> <p>Now how I worked it out was to take each number and enumerate the set of possibilites and then count all the distinct values. How I enumerated the set was to start with the number, add one to it and then OR it with itself until I reached the mask. With the number itself being in the set and the mask (being all set to 1) also in the set. So for example to enumerate the set of 1001:</p> <pre><code>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) </code></pre> <p>So do that for each number and then count the uniques.</p> <p>This is it in python code (but language doesn't really matter as long as you can do bitwise operations, hence why this question is tagged for c/c++ as well):</p> <pre><code>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 </code></pre> <p>Now this works and gives the correct answer but I'm wondering if I have missed a trick. Since the question was to only ask the count and not enumerate all the values perhaps there is a much quicker way. Either by combining the numbers first, or getting a count without enumeration. I have a feeling there is. Since numbers that contain lots of zeros the enumeration rises exponentially and it can take quite a while. </p> <p>If you have A B and C, the count of the set of numbers which has bits set to 1 where A or B or C has corresponding bits set to 1.</p> <p>Some people don't understand the question (didn't help that I didn't ask it correctly first of). Let's use the given A B and C values above:</p> <p>A:</p> <pre><code>1001 1011 1101 1111 </code></pre> <p>B:</p> <pre><code>0011 0111 1011 1111 </code></pre> <p>C:</p> <pre><code>0110 0111 1110 1111 </code></pre> <p>Now combine those sets and count the distinct entries. That is the answer. Is there a way to do this without enumerating the values?</p> <p>edit: Sorry for the mistake the question. Fixed now.</p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USdalore
    1. USdalore
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    3. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POCount bitmasks, enumerate 0s
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POCount bitmasks, enumerate 0s
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POCount bitmasks, enumerate 0s
      1. This table or related slice is empty.
      1. VTUpMod
    1. COI think this question would be a better fit for codegolf.
      singulars
      1. POCount bitmasks, enumerate 0s
      1. USJohn Dibling
    2. COI'm sorry I confused. Firstly you use & in the example and than | in your code. Secondly why isn't 1000 a solution in your example? Could you please clarify, I'm eager to understand :)
      singulars
      1. POCount bitmasks, enumerate 0s
      1. USther
    3. COAm I missing something here? When `0001` is ANDed with either `A` or `B` above, it gives a true. Why isn't that considered a possible solution?
      singulars
      1. POCount bitmasks, enumerate 0s
      1. USchrisaycock
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload