Leetcode bit operation

231. 2 The power of - Power button （LeetCode）

231. 2 The power of - Power button （LeetCode）

  Judge whether a number is 2 Of n Power , such as 16 yes ,5 No

Violence law ：

class Solution 
{
    public boolean isPowerOfTwo(int n) 
    {
        for(int i=0;Math.pow(2,i)<=n;i++)
        {
            if(Math.pow(2,i)==n)   return true;   
        }
        return false;
    }
}

If a number m yes 2 Of n Power , So its binary representation is 100000, The highest bit is 1, The others are 0

and m-1 The binary representation of is 011111, The highest bit is 0, Other bits are 1

therefore m&m-1=0

 

class Solution 
{
    public boolean isPowerOfTwo(int n) 
    {
        // Two test cases were found when submitting 0 and -2147483648
        // These two expectations are false, But our answer is true
        if(n<=0)   return false;
        return (n&(n-1))==0;   
    }
}

342. 4 The power of - Power button （LeetCode）

  The core ： First of all, the number must be 2 Of n Power , Next, divide this number by 3 The remainder must be 1, So this number is 4 The power of

class Solution
{
    public boolean isPowerOfFour(int n) 
    {
        return ((n&(n-1))==0)&&(n%3==1);
    }
}

191. position 1 The number of - Power button （LeetCode）

Put the input numbers in the following order 32 Number and operation , The result is not 0 Explain that the input number is 1, The result is 0 Explain that the input number is 0, With a number count The statistics bit is 1 Number of digits

  Move left 32 Secondary method ：

public class Solution
{
    // you need to treat n as an unsigned value
    public int hammingWeight(int n)
    {
        int count=0;

        int m=1;//32 The first number in the number ,0000.....0001

        for(int i=1;i<=32;i++)
        {
            if((n&m)!=0)  count++;
            m=m<<1;//m Move left 1 position            
        }
        return count;
    }
}

Of course, you can constantly input n Move right one bit , and 0000.....0001 To carry out and operate , Move right 32 Secondary method ：

public class Solution
{
    // you need to treat n as an unsigned value
    public int hammingWeight(int n)
    {
        int count=0;

        int m=1;
        for(int i=1;i<=32;i++)
        {
            if((n&m)!=0)  count++;
            n=n>>1;//n Move right 1 position            
        }
        return count;
    }
}

solution 3： Utilization property ：n&(n-1), The result of the operation is n The lowest bit in the binary representation of 1 become 0：

  Take advantage of this property , Constantly put the current n and n-1 Conduct & operation , until n become 0

public class Solution
{
    // you need to treat n as an unsigned value
    public int hammingWeight(int n)
    {
        int count=0;
    
        while(n!=0)
        {
            n=n&(n-1);
            count++;
        }
        return count;
    }
}

Interview questions 16.01. Exchange numbers - Power button （LeetCode）

Do not use intermediate variables to exchange two numbers

 

 

class Solution
 {
    public int[] swapNumbers(int[] numbers) 
    {

        numbers[0] = numbers[0] ^ numbers[1];
        numbers[1] = numbers[0] ^ numbers[1];
        numbers[0] = numbers[0] ^ numbers[1];
        return numbers;
    }
}

136. A number that appears only once - Power button （LeetCode）

A number that appears only once in an array （ The other numbers appear twice ）

Utilization property ：（1） Any number does XOR with itself （ Different from 1, A fellow 0）, The result is 0

                  （2)0 XOR with any number , The result is itself

class Solution 
{
    public int singleNonDuplicate(int[] nums)
    {
        int result=0;
        for(int num:nums)
        {
            result=result^num;
        }
        return result;
    }
}

461. Hamming distance - Power button （LeetCode）

That is to say, XOR the two numbers first , Then there is the topic of selling ： Seeking position 1 The number of

class Solution
 {
    public int hammingDistance(int x, int y) 
    {
        // Find out first x^y, namely x and y By doing XOR operation, we can find out how many bits are different between these two numbers 

        // Then look at the results of several 1 You will know the distance between Han and Ming 
        // How do you think there are several in the binary representation of a number 1 Well ？x=x&（x-1） How many times x To become 0
        int temp=x^y;
        int result=0;
        while(temp!=0)
        {
            result++;
            temp=temp&(temp-1);
        }
        return result;
    }
}