Detailed explanation and generalization of the bitwise operation method for single numbers


  • 435
    F

    I -- Statement of our problem

    "Given an array of integers, every element appears k (k > 1) times except for one, which appears p times (p >= 1, p % k != 0). Find that single one."


    II -- Special case with 1-bit numbers

    As others pointed out, in order to apply the bitwise operations, we should rethink how integers are represented in computers -- by bits. To start, let's consider only one bit for now. Suppose we have an array of 1-bit numbers (which can only be 0 or 1), we'd like to count the number of 1's in the array such that whenever the counted number of 1 reaches a certain value, say k, the count returns to zero and starts over (in case you are curious, this k will be the same as the one in the problem statement above). To keep track of how many 1's we have encountered so far, we need a counter. Suppose the counter has m bits in binary form: xm, ..., x1 (from most significant bit to least significant bit). We can conclude at least the following four properties of the counter:

    1. There is an initial state of the counter, which for simplicity is zero;
    2. For each input from the array, if we hit a 0, the counter should remain unchanged;
    3. For each input from the array, if we hit a 1, the counter should increase by one;
    4. In order to cover k counts, we require 2^m >= k, which implies m >= logk.

    Here is the key part: how each bit in the counter (x1 to xm) changes as we are scanning the array. Note we are prompted to use bitwise operations. In order to satisfy the second property, recall what bitwise operations will not change the operand if the other operand is 0? Yes, you got it: x = x | 0 and x = x ^ 0.

    Okay, we have an expression now: x = x | i or x = x ^ i, where i is the scanned element from the array. Which one is better? We don't know yet. So, let's just do the actual counting.

    At the beginning, all bits of the counter is initialized to zero, i.e., xm = 0, ..., x1 = 0. Since we are gonna choose bitwise operations that guarantee all bits of the counter remain unchanged if we hit 0's, the counter will be 0 until we hit the first 1 in the array. After we hit the first 1, we got: xm = 0, ...,x2 = 0, x1 = 1. Let's continue until we hit the second 1, after which we have: xm = 0, ..., x2 = 1, x1 = 0. Note that x1 changed from 1 to 0. For x1 = x1 | i, after the second count, x1 will still be 1. So it's clear we should use x1 = x1 ^ i. What about x2, ..., xm? The idea is to find the condition under which x2, ..., xm will change their values. Take x2 as an example. If we hit a 1 and need to change the value of x2, what must be the value of x1 right before we do the change? The answer is: x1 must be 1 otherwise we shouldn't change x2 because changing x1 from 0 to 1 will do the job. So x2 will change value only if x1 and i are both 1, or mathematically, x2 = x2 ^ (x1 & i). Similarly xm will change value only when xm-1, ..., x1 and i are all 1: xm = xm ^ (xm-1 & ... & x1 & i). Bingo, we've found the bitwise operations!

    However, you may notice that the bitwise operations found above will count from 0 until 2^m - 1, instead of k. If k < 2^m - 1, we need some "cutting" mechanism to reinitialize the counter to 0 when the count reaches k. To this end, we apply bitwise AND to xm,..., x1 with some variable called mask, i.e., xm = xm & mask, ..., x1 = x1 & mask. If we can make sure that mask will be 0 only when the count reaches k and be 1 for all other count cases, then we are done. How do we achieve that? Try to think what distinguishes the case with k count from all other count cases. Yes, it's the count of 1's! For each count, we have unique values for each bit of the counter, which can be regarded as its state. If we write k in its binary form: km,..., k1. we can construct mask as follows:

    mask = ~(y1 & y2 & ... & ym), where yj = xj if kj = 1, and yj = ~xj if kj = 0 (j = 1 to m).

    Let's do some examples:

    k = 3: k1 = 1, k2 = 1, mask = ~(x1 & x2);

    k = 5: k1 = 1, k2 = 0, k3 = 1, mask = ~(x1 & ~x2 & x3);

    In summary, our algorithm will go like this (nums is the input array):

    for (int i : nums) {
        xm ^= (xm-1 & ... & x1 & i);
        xm-1 ^= (xm-2 & ... & x1 & i);
        .....
        x1 ^= i;
        
        mask = ~(y1 & y2 & ... & ym) where yj = xj if kj = 1, and yj = ~xj if kj = 0 (j = 1 to m).
    
        xm &= mask;
        ......
        x1 &= mask;
    }
    

    III -- General case with 32-bit numbers

    Now it's time to generalize our results from 1-bit number case to 32-bit integers. One straightforward way would be creating 32 counters for each bit in the integer. You've probably already seen this in other posted solutions. However, if we take advantage of bitwise operations, we may be able to manage all the 32 counters "collectively". By saying "collectively", we mean using m 32-bit integers instead of 32 m-bit counters, where m is the minimum integer that satisfies m >= logk. The reason is that bitwise operations apply only to each bit so operations on different bits are independent of each other (kind obvious, right?). This allows us to group the corresponding bits of the 32 counters into one 32-bit integer. Here is a schematic diagram showing how this is done.

    0_1510941016426_137. Single Number II .png

    The top row is the 32-bit integer, where for each bit, we have a corresponding m-bit counter (shown by the column below the upward arrow). Since bitwise operations on each of the 32 bits are independent of each other, we can group, say the m-th bit of all counters, into one 32-bit number (shown by the orange box). All bits in this 32-bit number (denoted as xm) will follow the same bitwise operations. Since each counter has m bits, we end up with m 32-bit numbers, which correspond to x1, ..., xm defined in part II, but now they are 32-bit integers instead of 1-bit numbers. Therefore, in the algorithm developed above, we just need to regard x1 to xm as 32-bit integers instead of 1-bit numbers. Everything else will be the same and we are done. Easy, hum?


    IV -- What to return

    The last thing is what value we should return, or equivalently which one of x1 to xm will equal the single element. To get the correct answer, we need to understand what the m 32-bit integers x1 to xm represent. Take x1 as an example. x1 has 32 bits and let's label them as r (r = 1 to 32). After we are done scanning the input array, the value for the r-th bit of x1 will be determined by the r-th bit of all the elements in the array (more specifically, suppose the total count of 1 for the r-th bit of all the elements in the array is q, q' = q % k and in its binary form: q'm,...,q'1, then by definition the r-th bit of x1 will be equal to q'1). Now you can ask yourself this question: what does it imply if the r-th bit of x1 is 1?

    The answer is to find what can contribute to this 1. Will an element that appears k times contribute? No. Why? Because for an element to contribute, it has to satisfy at least two conditions at the same time: the r-th bit of this element is 1 and the number of appearance of this 1 is not an integer multiple of k. The first condition is trivial. The second comes from the fact that whenever the number of 1 hit is k, the counter will go back to zero, which means the corresponding bit in x1 will be reset to 0. For an element that appears k times, it's impossible to meet these two conditions simultaneously so it won't contribute. At last, only the single element which appears p (p % k != 0) times will contribute. If p > k, then the first k * [p/k] ([p/k]denotes the integer part of p/k) single elements won't contribute either. So we can always set p' = p % k and say the single element appears effectively p' times.

    Let's write p' in its binary form: p'm, ..., p'1 (note that p' < k, so it will fit into m bits). Here I claim the condition for xj to equal the single element is p'j = 1 (j = 1 to m), with a quick proof given below.

    If the r-th bit of xj is 1, we can safely say the r-th bit of the single element is also 1 (otherwise nothing can make the r-th bit of xj to be 1). We are left to prove that if the r-th bit of xj is 0, then the r-th bit of the single element can only be 0. Just suppose in this case the r-th bit of the single element is 1, let's see what will happen. At the end of the scan, this 1 will be counted p' times. By definition the r-th bit of xj will be equal to p'j, which is 1. This contradicts with the presumption that the r-th bit of xj is 0. Therefore we conclude the r-th bit of xj will always be the same as the r-th bit of the single number as long as p'j = 1. Since this is true for all bits in xj (i.e., true for r = 1 to 32), we conclude xj will equal the single element as long as p'j = 1.

    So now it's clear what we should return. Just express p' = p % k in its binary form and return any of the corresponding xj as long as p'j = 1. In total, the algorithm will run in O(n * logk) time and O(logk) space.


    Side note: There is a general formula relating each bit of xj to p'j and each bit of the single number s, which is given by (xj)_r = s_r & p'j, with (xj)_r and s_r denoting respectively the r-th bit of xj and the single number s. From this formula, it's easy to see that (xj)_r = s_r if p'j = 1, that is, xj = s as long as p'j = 1, as shown above. Furthermore, we have (xj)_r = 0 if p'j = 0, regardless of the value of the single number, that is, xj = 0 as long as p'j = 0. So in summary we obtain: xj = s if p'j = 1, and xj = 0 if p'j = 0. This implies the expression (x1 | x2 | ... | xm) will also be evaluated to the single number s, since the expression will essentially take the OR operations of the single number with itself and some 0s, which boils down to the single number eventually.


    V -- Quick examples

    Here is a list of few quick examples to show how the algorithm works (you can easily come up with other examples):

    1. k = 2, p = 1
      k is 2, then m = 1, we need only one 32-bit integer (x1) as the counter. And 2^m = k so we do not even need a mask! A complete java program will look like:
        public int singleNumber(int[] nums) {
            int x1 = 0;
             
            for (int i : nums) {
                x1 ^= i;
            }
             
            return x1;
        }
    
    1. k = 3, p = 1
      k is 3, then m = 2, we need two 32-bit integers(x2, x1) as the counter. And 2^m > k so we do need a mask. Write k in its binary form: k = '11', then k1 = 1, k2 = 1, so we have mask = ~(x1 & x2). A complete java program will look like:
        public int singleNumber(int[] nums) {
            int x1 = 0, x2 = 0, mask = 0;
             
            for (int i : nums) {
                x2 ^= x1 & i;
                x1 ^= i;
                mask = ~(x1 & x2);
                x2 &= mask;
                x1 &= mask;
            }
    
            return x1;  // Since p = 1, in binary form p = '01', then p1 = 1, so we should return x1. 
                        // If p = 2, in binary form p = '10', then p2 = 1, and we should return x2.
                        // Or alternatively we can simply return (x1 | x2).
        }
    
    1. k = 5, p = 3
      k is 5, then m = 3, we need three 32-bit integers(x3, x2, x1) as the counter. And 2^m > k so we need a mask. Write k in its binary form: k = '101', then k1 = 1, k2 = 0, k3 = 1, so we have mask = ~(x1 & ~x2 & x3). A complete java program will look like:
        public int singleNumber(int[] nums) {
            int x1 = 0, x2 = 0, x3  = 0, mask = 0;
       
            for (int i : nums) {
                x3 ^= x2 & x1 & i;
                x2 ^= x1 & i;
                x1 ^= i;
                mask = ~(x1 & ~x2 & x3);
                x3 &= mask;
                x2 &= mask;
                x1 &= mask;
            }
            
            return x1;  // Since p = 3, in binary form p = '011', then p1 = p2 = 1, so we can return either x1 or x2. 
                        // If p = 4, in binary form p = '100', only p3 = 1, which implies we can only return x3.
                        // Or alternatively we can simply return (x1 | x2 | x3).
        }
    

    Lastly I would like to thank those for providing feedbacks to make this post better. Hope it helps and happy coding!


  • 113
    F

    Here is a list of few quick examples to show how the algorithm works:

    1. k = 2, p = 1
      k is 2, then m = 1, we need only one 32-bit integer(x1) as the counter. And 2^m = k so we do not even need a mask! A complete java program will look like:
        public int singleNumber(int[] A) {
             int x1 = 0;
             
             for (int i : A) {
                 x1 ^= i;
             }
             
             return x1;
        }
    
    1. k = 3, p = 1
      k is 3, then m = 2, we need two 32-bit integers(x2, x1) as the counter. And 2^m > k so we do need a mask. Write k in its binary form: k = '11', then k1 = 1, k2 = 1, so we have mask = ~(x1 & x2). A complete java program will look like:
        public int singleNumber(int[] A) {
             int x1 = 0, x2 = 0, mask = 0;
       
             for (int i : A) {
                 x2 ^= x1 & i;
                 x1 ^= i;
                 mask = ~(x1 & x2);
                 x2 &= mask;
                 x1 &= mask;
             }
    
             return x1;  // p = 1, in binary form p = '01', then p1 = 1, so we should return x1; 
                         // if p = 2, in binary form p = '10', then p2 = 1, so we should return x2.
        }
    
    1. k = 5, p = 3
      k is 5, then m = 3, we need three 32-bit integers(x3, x2, x1) as the counter. And 2^m > k so we need a mask. Write k in its binary form: k = '101', then k1 = 1, k2 = 0, k3 = 1, so we have mask = ~(x1 & ~x2 & x3). A complete java program will look like:
        public int singleNumber(int[] A) {
             int x1 = 0, x2 = 0, x3  = 0, mask = 0;
       
             for (int i : A) {
                 x3 ^= x2 & x1 & i;
                 x2 ^= x1 & i;
                 x1 ^= i;
                 mask = ~(x1 & ~x2 & x3);
                 x3 &= mask;
                 x2 &= mask;
                 x1 &= mask;
             }
           
             return x1;  // p = 3, in binary form p = '011', then p1 = p2 = 1, so we can
                         // return either x1 or x2. But if p = 4, in binary form p = '100', 
                         // only p3 = 1, which implies we can only return x3.
        }
    

    You can easily come up with other examples. If you have any questions about the explanation, please let me know. I would appreciate your feedback. Thanks!


  • 7
    P

    Thank you for your method. I have made my code.

    int singleNumber(int* nums, int numsSize, int k) //k>=2
    {
        int counter[32];
        int i, j;
        int res = 0;
        
        for(i=0; i<32; i++)
            counter[i] = 0;
            
        for(i=0; i<numsSize; i++)
        {
            for(j=0; j<32; j++)
            {
                if(nums[i] & (1<<j))
                    counter[j]++;
            }
        }
        
        for(i=0; i<32; i++)
        {
            if(counter[i]%k)
                res |= 1<<i;
        }
        
        return res;
    }
    

    It seems that this method is slower than some other methods when k==3. But I think that your method will be more universal and quicker when k is a big number.


  • 1
    L

    nice explanation... I suppose the condition 'p != k' is not sufficient for your algorithm to work - shouldn't it rather be 'p%k != 0'?


  • 0
    F

    Hi, langermatze. Nice catch! Thanks!


  • 3
    S

    thank you! It's the best answer I've ever seen!


  • 5
    W

    Here is my code for this general solution. Thank you for the detailed explanation.

    public class Solution {
        public int singleNumber(int[] nums) {
        	return generalSolution(nums, 3, 1);
        }
        public int generalSolution(int[] nums, int all_rep, int single_rep) {
    		int m = bit_length(all_rep);
    		int[] counters = new int[m];
    		for (int n : nums) {
    			//counting
    			for (int i = m-1; i >=0; i--) {
    				int carr = n;
    				for (int j = i-1; j >= 0; j--) {
    					carr &= counters[j];
    				}
    				counters[i] ^= carr;
    			}
    			//mask
    			int mask = ~0;
    			for (int i = m-1; i >= 0; i--) {
    				if (((all_rep >> i) & 1) == 1) {
    					mask &= counters[i];
    				} else {
    					mask &= ~counters[i];
    				}
    			}
    			mask = ~mask;
    			
    			for (int i = m-1; i>=0; i--) {
    				counters[i] &= mask;
    			}
    
    		}
    		//find the return value
    		single_rep %= all_rep;
    		for (int i = 0; single_rep != 0; i++) {
    			if ((single_rep & 1) == 1) {
    				return counters[i];
    			} else {
    				single_rep >>= 1;
    			}
    		}
    		return -1;  //error
    	}
    	public int bit_length( int bits ) {
    		int res = 0;
    		while (bits > 0) {
    		    bits >>= 1;	
    		    res++;
    		}
    		return res;
    	}
    }

  • 0
    C

    It can extend to p % k == 0 and p !=k. Just select a module instead of k that can separate k and p. for example, p = 6, k = 3, we can store the 1-6 count of bit, the answer is the 6th count of bit, i.e. k6 in your expression.


  • 2
    K

    One optimization to make it a little faster:

    instead of

        //counting
        for (int i = m-1; i >=0; i--) {
            int carr = n;
            for (int j = i-1; j >= 0; j--) {
                carr &= counters[j];
            }
            counters[i] ^= carr;
        }
    

    we can use this:

        int carr = num;
        int temp = 0;
        for(int i = 0; i < m; i++){
            temp = carr & counters[i];
            counters[i] ^= carr;
            carr = temp;
        }
    

    to eliminate the inner loop


  • 0
    B

    excellent explanation!


  • 0
    D

    This is a terribly good answer! I love it!


  • 2
    E

    If leetCode could support latex, such as mathjax, it will great pleasure to read the answers. I read slowly when encounter mj, xk,.. and so on.


  • 0
    M

    Thanks for the great explanation. One more clarification, to find the single element, can you just take the 'bitwise or' of all the xjs?


  • 1
    C

    This is a great universal solution!
    I translate it into Chinese with better format
    http://chihiroxc.me/2016/09/04/algorithm-single-number/


  • 0
    B

    I'm confused about why we can convert the counter to m 32-bit from 32 m-bit. The other parts are clear except for this part. Could you please provide more details?


  • 0
    B

    @fun4LeetCode Can you explain why we can convert the counter from 32 m-bit to m 32-bit? I find difficulties understanding this part. Thanks.


  • 11
    F

    @bd117 Hi bd117. I think the conversion is best to be understood with illustration. So I drew the following diagram: 0_1476111650417_Single number.JPG

    Here is a quick explanation of the diagram:

    The first 32-bit integer represents the input number. For each bit of the input integer, we have an m-bit counter, whose bits are labelled from 1st to mth as shown in the diagram. Let's take the 1st bit of all the 32 m-bit counters as an example. I have shown that all these 1st bits follow the same "transformation sequence" (same bitwise operations), therefore we can regroup them into a single 32-bit integer. Similarly for the 2nd up to the mth bits of the counters. Each of them can form a single 32-bit integer and we end up with m 32-bit integers.

    Remember the key here is that all bits of the same order (i.e., all 1st bits, all 2nd bits, ..., all mth bits) in the original 32 counters will undergo the same bitwise operations, so we can collect and rearrange them to form an integer.

    Let me know if this clears it up for you.


  • 0
    B

    @fun4LeetCode Thanks a lot. So if "0" appear on r-th bit of x1, all the other value on r-th bit of x2...xm must be "0", otherwise, such case will happen that the count of "1" on i-th bit is 19 while the count of "0" is 18. It can't happen. That's why we can return any xi that has "1" on some bit in the end. Am I correct?


  • 1
    F

    @bd117 Hi bd117. Remember that values of the rth bit of x1, x2, ..., xm are not related to each other. They are determined only by the total count of "1" bits of the rth bit of all the input integers. Actually if you rearrange the rth bit of x1, x2, ..., xm, you will get the original counter back for the rth bit of the input integers (refer to the diagram above).

    What I was showing in the last part is the condition for xk to be equal to the single number. We know that if all the bits of two integers are the same, they will be equal to each other. And I proved that all the bits of xk will be the same as all the bits of the single number if the kth bit of p' (p' = p%k) is 1. That is to say, provided the kth bit of p' is 1, then if the 1st bit of xk is 0, the 1st bit of the single number will also be 0. If the 1st bit of xk is 1, then the 1st bit of the single number will be 1. This is true for all the 2nd, 3rd, 4th, ..., 32nd bits. So if the kth bit of p' is 1, xk will be equal to the single number and it can be returned as the answer.


  • 0

    This tutorial is amazing. Thanks a lot for sharing.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.