Bit manipulation implementation


  • 8
    G
    public int majorityElement2(int[] num)
    {
    	int majority = 0;
    	for (int p = 0; p < 32; p++)
    	{
    		int count0 = 0;
    		int count1 = 0;
    		for (int value : num)
    		{
    			if (getIntegerBit(value, p))
    				count1++;
    			else
    				count0++;
    		}
    
    		if (count0 > count1) 
    			majority = majority & ~(1 << p);
    		else
    			majority = majority | (1 << p);
    	}
    	return majority;
    }
    
    public boolean getIntegerBit(int value, int p)
    {
    	if (p >= 32)
    		throw new IllegalArgumentException("");
    	return (value & (1L << p)) != 0;
    }
    

    This algorithm is 20 times slower than Moore voting algorithm.

    Array size: 2147483

    Moore voting algorithm run time: 6419218 ns

    Bit manipulation run time:        142345391 ns


Log in to reply
 

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