Leetcode之位运算总结

这篇文章总结目前我做过的位运算相关习题，在之后的刷题过程中将会不断扩充此专题。题目列表如下：
1. 190 颠倒的二进制位
2. 191 位1的个数
3. 231 2的幂
4. 371 两整数之和
5. 405 数字转化为十六进制

190 颠倒的二进制位

题目大意

颠倒给定的 32 位无符号整数的二进制位。
示例1：

输入: 00000010100101000001111010011100
输出: 00111001011110000010100101000000
解释: 输入的二进制串 00000010100101000001111010011100 表示无符号整数 43261596，
因此返回 964176192，其二进制表示形式为 00111001011110000010100101000000。

示例2：

输入：11111111111111111111111111111101
输出：10111111111111111111111111111111
解释：输入的二进制串 11111111111111111111111111111101 表示无符号整数 4294967293，
因此返回 3221225471 其二进制表示形式为 10101111110010110010011101101001。

思路

利用位运算，原数每次循环右移1位，取末尾数字，然后新数加上这个末尾再循环左移。

代码

 public int reverseBits(int n) {
        int t = 0;
        for(int i = 0;i<32;i++) 
            t+= (1&(n>>i))<<(31-i);
        return t;
    }

运行时间2ms。

位1的个数

题目大意

编写一个函数，输入是一个无符号整数，返回其二进制表达式中数字位数为 ‘1’ 的个数。
示例1：

输入：00000000000000000000000000001011
输出：3
解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。

示例2：

输入：00000000000000000000000010000000
输出：1
解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 '1'。

思路一：位运算

利用循环右移操作，每次移动1位，并且取出末尾与1做&操作，若不为1，说明末尾是0。

public int hammingWeight(int n) {
         int cnt = 0;
        for(int i=0;i<32;i++)
        {
            cnt += n&1;
            n >>=1;
        }
        return cnt;
    }

思路二：n与n-1做位运算

当n与n-1做&运算，会把最后一个1的位变成0。

image.png

 public int hammingWeight(int n) {
        int cnt = 0;
        while(n!=0) {
           ++cnt;
           n = n&(n-1);
        }
        return cnt;
    }

运行时间2ms。

231 2的幂

题目大意

给定一个整数，编写一个函数来判断它是否是 2 的幂次方。
示例1：

输入: 1
输出: true
解释: 2^0 = 1

示例2：

输入: 16
输出: true
解释: 24 = 16

方法一：暴力法

采用迭代的方法，一个一个试。此题会超时。

public boolean isPowerOfTwo(int n) {
        if(n==1) return true;
        int cur = 1;
        while(cur<n) {
            cur *=2;
            if(cur==n) return true;
        }
        return false;
    }

方法二：二分查找

采用打表和二分查找的方法，将int范围内的所有2^n全部存入一个整数表中，然后对整数表进行二分查找。

int[] res = new int[31];
private void form() {
        res[0] = 1;
        for(int i=1;i<31;i++)
            res[i]=res[i-1]*2;
    }
public boolean isPowerOfTwo(int n) {
        form();
        if(n!=1 && n%2==1) return false;
        int low = 0;
        int high = 30;
        while(low<high) {
            int mid = (low+high)>>1;
            if(res[mid]==n) return true;
            else if(res[mid] > n)
                high = mid -1;
            else if(res[mid] < n)
                low = mid+1;
        }
        return res[low]==n?true:false;
    }

运行时间3ms,87.42%。

方法三：位运算

将2^n 和 2^n-1做与运算，结果一定为0。

 public boolean isPowerOfTwo(int n) {
        if(n<=0) return false;
        return (n&(n-1))==0?true:false;
    }

运行时间2ms, 98.23%。

两整数之和

题目大意

不使用运算符 + 和 - ，计算两整数 a 、b 之和。
示例1：

输入: a = 1, b = 2
输出: 3

输入: a = -2, b = 3
输出: 1

思路

不用运算符，考虑位运算。a^b 得到不考虑进位的a+b结果；a&b<<1得到a+b的进位。

image.png

public int getSum(int a, int b) {
        while(b!=0) {
            int carry = (a&b)<<1;
            a = a^b;
            b = carry;
        }
        return a;
    }

405 数字转化为十六进制

题目大意

给定一个整数，编写一个算法将这个数转换为十六进制数。对于负整数，我们通常使用补码运算。
注意：

十六进制中所有字母(a-f)都必须是小写。
十六进制字符串中不能包含多余的前导零。如果要转化的数为0，那么以单个字符'0'来表示；对于其他情况，十六进制字符串中的第一个字符将不会是0字符。
给定的数确保在32位有符号整数范围内。
不能使用任何由库提供的将数字直接转换或格式化为十六进制的方法。

示例1：

输入:
26

输出:
"1a"

示例2：

输入:
-1

输出:
"ffffffff"

方法：位运算

public String toHex(int num) {
        if(num==0) return "0";
        char[] dict = {'0','1','2','3','4','5','6','7','8','9',
            'a','b','c','d','e','f'};
        StringBuffer sb = new StringBuffer();
        while(num!=0) {
            sb.append(dict[num&0xf]);
            num = num >>> 4;
        }
        return sb.reverse().toString();
    }

&0xf: 取末尾四位。
运行时间1ms,击败88.12%。

Leetcode之位运算总结