leetcode-位运算

231. 2 的幂 - 力扣（LeetCode）

231. 2 的幂 - 力扣（LeetCode）

 判断一个数是否是2的n次方，比如16是，5不是

暴力法：

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;
    }
}

如果一个数m是2的n次方，那么它的二进制表示就是100000，最高位为1，其他位都是0

而m-1的二进制表示就是011111，最高位为0，其他位为1

所以m&m-1=0

 

class Solution 
{
    public boolean isPowerOfTwo(int n) 
    {
        //提交时发现有两个测试用例0和-2147483648
        //这两个预期都是false，但是我们答案得到的是true
        if(n<=0)   return false;
        return (n&(n-1))==0;   
    }
}

342. 4的幂 - 力扣（LeetCode）

 核心：首先这个数得是2的n次方，其次这个数除以3余数必须为1，那么这个数就是4的幂

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

191. 位1的个数 - 力扣（LeetCode）

将输进来的数依次和下面32个数进行与操作，结果不为0说明输进来的数这一位是1,结果为0说明输进来的数这一位是0，用一个数count来统计位为1的位数

 左移32次法：

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

        int m=1;//32个数中的第一个数，0000.....0001

        for(int i=1;i<=32;i++)
        {
            if((n&m)!=0)  count++;
            m=m<<1;//m左移1位           
        }
        return count;
    }
}

当然你也可以不断的将输入的n进行右移一位，和0000.....0001来进行与操作，右移32次法：

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右移1位           
        }
        return count;
    }
}

解法3：利用性质：n&(n-1)，运算结果是把n的二进制表示中的最低位的1变成0：

 利用这个性质，不断的将当前n和n-1进行&操作，直到n变成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;
    }
}

面试题 16.01. 交换数字 - 力扣（LeetCode）

不使用中间变量交换两个数字

 

 

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. 只出现一次的数字 - 力扣（LeetCode）

数组中只出现一次的数（其他数都出现两次）

利用性质：（1）任何数和自己做异或（异为1，同为0），结果都为0

                  （2)0和任何数做异或，结果为本身

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

461. 汉明距离 - 力扣（LeetCode）

也就是说先将两个数进行异或运算，然后就是上卖那道题目了：求位1的个数

class Solution
 {
    public int hammingDistance(int x, int y) 
    {
        //先求出x^y,即x和y做异或运算就可以求出这两个数之间有多少位不一样了

        //然后看结果中有几位1就知道汉明距离是多少了
        //那怎么看一个数的二进制表示里面有几个1呢？x=x&（x-1）看几次x才能变为0
        int temp=x^y;
        int result=0;
        while(temp!=0)
        {
            result++;
            temp=temp&(temp-1);
        }
        return result;
    }
}