ITeye博客

Bit Manipulation总结(二)

KickCode · 2015-12-15 17:12 · Leetcode · 编程语言 · Markdown

这篇文章介绍通过位运算求解子集,反转二进制数,判断是否为2的幂等。

1,Number of 1 Bits 给定一个无符号的整数,输出它包含1的个数。

通过右移,依次与1位与,得到1的个数。 代码如下:


public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int count = 0;
        for(int i = 0; i < 32; i++) {
            if((n >> i & 1) == 1) {
                count ++;
            }
        }
        return count;
    }
}

2,Subsets 给定一个没有重复元素的数组,输出所有的子集。 例如:给定nums = {1,2,3} 输出:, , , , ,,, ]

我们知道长度为n的集合,子集的个数为2的n次方个,我们通过0到2^n - 1正好可以表示子集的状态,具体代码如下:


public class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<Integer> list = new ArrayList<Integer>();
        List<List<Integer>> llist = new ArrayList<List<Integer>>();
        Arrays.sort(nums);
        int helper = 1;
        for(int i = 0; i < Math.pow(2, nums.length); i++) {
            for(int j = 0; j < nums.length; j++) {
                if(((i >> j) & helper) == 1) {
                    list.add(nums[j]);
                }
            }
            llist.add(new ArrayList<Integer>(list));
            list.clear();
        }
        return llist;
    }
}

3,Reverse Bits 给定一个无符号整数n,将它的二进制序列反转。

我们每次取n的最后一位,然后再通过左移,得到最终结果。 代码如下:


public class Solution {
    // you need treat n as an unsigned value
    public int reverseBits(int n) {
        int result = 0;
        for(int i = 0; i < 32; i++) {
            result = result << 1;
            result |= ((n >> i)& 1);
        }
        return result;
    }
}

4,Bitwise AND of Numbers Range 给定一个范围,将这个区间所有的数字位与,包括m和n, 0 <= m <= n <= 2147483647,输出最后结果。 例如,给定,输出:4

进行位与操作,位上有一个0,那么这个位置上肯定为0,因此我们只要从高位开始比较m和n,只要他们相等的位我们就保留,如果不相等就终止,因为后面肯定全为0。因为0 <= m <= n <= 2147483647,因此要把mask设定为长整型,因为把1左移31位后,如果是int型,最高位为符号位,与题意不符。代码如下:


public class Solution {
    public int rangeBitwiseAnd(int m, int n) {
        int result = 0;
        long mask = 1L << 31;
        while(mask > 0) {
            if((m & mask) == (n & mask)) {
                result |= (n & mask);
            } else {
                break;
            }
            mask = mask >> 1;
        }
        return result;
    }
}

评论(0)

暂无评论。

评论功能维护中,当前仅展示历史评论。