Bit manipulation solution for majority element in an array
<p>Source: <a href="https://discuss.leetcode.com/topic/28601/java-solutions-sorting-hashmap-moore-voting-bit-manipulation/2" rel="nofollow noreferrer">https://discuss.leetcode.com/topic/28601/java-solutions-sorting-hashmap-moore-voting-bit-manipulation/2</a></p>

<p>Q: Identify the element that appears most in an array.
I was able to solve it but was curious to look at others' solutions. So I came across the solution which uses bit-manipulation.</p>

<pre><code>public int majorityElement(int[] nums) {
    int[] bit = new int[32];
    for (int num: nums)
        for (int i=0; i&lt;32; i++) 
            if ((num&gt;&gt;(31-i) &amp; 1) == 1)
                bit[i]++;
    int ret=0;
    for (int i=0; i&lt;32; i++) {
        bit[i]=bit[i]&gt;nums.length/2?1:0;
        ret += bit[i]*(1&lt;&lt;(31-i));
    }
    return ret;
}
</code></pre>

<p>When I replace the line  </p>

<pre><code>ret += bit[i]*(1&lt;&lt;(31-i)); 
</code></pre>

<p>with</p>

<pre><code>ret += bit[i]*(1&lt;&lt;i);
</code></pre>

<p>I end up getting a negative number.</p>

<p>Consider the input array - [2, 5, 5, 5, 3], after the first for loop, bit[0] will contain 4, bit[1] = 2, bit[3] = 3 and all the other bits will be 0.</p>

<p>As per my understanding, the second for loop will result in the number whose bit positions 31 and 29 set to 1 (which is not same as 5).
I am clearly missing something in my understanding.</p>

<p>Can someone please explain how does this code work?
Thanks.</p>