位操作总结

小灰灰 2022-08-04 05:14 98阅读 0赞

有一类题是位操作，但是感觉在面试中，很少有这种题，毕竟不需要那么细的操作，感觉位操作在汇编和C语言关系比较大，比较偏底层。但是有时候用位操作往往得到意想不到的效果。

[http://graphics.stanford.edu/~seander/bithacks.html][http_graphics.stanford.edu_seander_bithacks.html]关于常见的为操作可以看这链接，将了好多方法，现将比较常见的整理一下。

一、位的基本操作

基本操作主要有六种，与、或、异或、取反、左移和右移

异或的三个主要特点：

1）任何数跟0异或，都是数本身。

2）任何数跟1异或，相当于把数进行取反。

3）任何数跟本身异或，结果都是0。

**注意：**在Java中的移位，<< 左移，右移分带符号右移>>和无符号右移>>>。带符号右移是指在以补数表示负数的时候，右移的时候高位会补1，而>>>无符号右移就不会。

二、常见用途或常见题型

1）可以判断是奇数还是偶数，对一个数进行乘以或除以2。都可以使用为操作，

//判断是否为奇数
    n & 0x1 == 1

2) 交换两个数字：

public void swap(int[] nums, int i, int j) {
        if (nums[i] != nums[j]) {
            nums[i] ^= nums[j];
            nums[j] ^= nums[i];
            nums[i] ^= nums[j];
        }
    }

3) 判断两个数字是否异号

boolean f = ((x ^ y) < 0);

4) 判断一个数是否为 [2的次幂][2]

public boolean isPowerOfTwo(int n) {
            return (n > 0) && ((n & (n-1)) == 0);
        }

n-1这种运算在位运算中还是比较常见的，比如

(1 << n) - 1 //把低n位全部设为1

还有在求二进制中1的个数是也用了这个特性 [http://blog.csdn.net/my\_jobs/article/details/43303601][http_blog.csdn.net_my_jobs_article_details_43303601]

5）setBit和getBit操作：

//index start by 0
        private boolean getBit(int n, int index) {
        	return (n & 1 << index) > 0;
        }
        
        public int setBit(int n, int inex, boolean b) {
        	if (b) return n | (1 << inex); // true set this bit to 1
        	return n & ~(1 << inex); // set this bit to o
        }

6）交换32 位整型的奇数位和偶数位

public int swapOddEvenBits(int x) { 
        	return ( ((x & 0xaaaaaaaa) >> 1) | ((x & 0x55555555) << 1) );
        }

7）反转32位整型数[reverseBits][]

public int reverseBits(int n) {
            n = (n >>> 16) | (n << 16);
            n = ((n & 0xff00ff00) >>> 8) | ((n & 0x00ff00ff) << 8);
            n = ((n & 0xf0f0f0f0) >>> 4) | ((n & 0x0f0f0f0f) << 4);
            n = ((n & 0xcccccccc) >>> 2) | ((n & 0x33333333) << 2);
            n = ((n & 0xaaaaaaaa) >>> 1) | ((n & 0x55555555) << 1);
            return n; 
        }

8）判断singleNumber。LeetCode的几道题，看这里[http://blog.csdn.net/my\_jobs/article/details/47731343][http_blog.csdn.net_my_jobs_article_details_47731343]

[http_graphics.stanford.edu_seander_bithacks.html]: http://graphics.stanford.edu/~seander/bithacks.html
[2]: https://leetcode.com/problems/power-of-two/
[http_blog.csdn.net_my_jobs_article_details_43303601]: http://blog.csdn.net/my_jobs/article/details/43303601
[reverseBits]: https://leetcode.com/problems/reverse-bits/
[http_blog.csdn.net_my_jobs_article_details_47731343]: http://blog.csdn.net/my_jobs/article/details/47731343