初识位运算

迷南。 2022-09-10 11:13 156阅读 0赞

初识计算机时就听说过一句话，计算机只认识0和，在现代计算机中所有的数据在内存中都是以二进制存在的。位运算直接对位进行操作，如果使用得好，很多时候能够取得很好的效果，下面简要的计算几种常见的位运算及其位运算相关的题。

1、与（**&**）运算符

只有当两位都是 1 时结果才是 1，否则为 0  
![20210907185929245.png][]

2、或（**|**）运算符

只有当两位都是 0 时结果才为 0，否则为 1

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_12_color_FFFFFF_t_70_g_se_x_16][]

3、异或（**^**）运算符

当两位相同时，则结果为 0，两位不同时结果为 1

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_15_color_FFFFFF_t_70_g_se_x_16][]

4、取反（**~**）运算符

位的值为 0 则变为 1 ，位的值为 1 则变为 0 。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_14_color_FFFFFF_t_70_g_se_x_16][]

5、**左移（<<）**：向左进行移位操作，高位丢弃，低位补 0

int a = 8;
    a << 3;
    移位前：00000000000000000000000000001000
    移位后：00000000000000000000000001000000

6、带符号的**右移（>> ）**：向右进行移位操作，对无符号数，高位补 0，对于有符号数，高位补符号位

unsigned int a = 8;
    a >> 3;
    移位前：00000000000000000000000000001000
    移位后：00000000000000000000000000000001
    
    int a = -8;
    a >> 3;
    移位前：11111111111111111111111111111000
    移位后：11111111111111111111111111111111

7、表示无符号的右移。按照二进制把数字右移指定数位，高位直接补零，低位移除。

**前面介绍了几种常用的运算符，这些运算符的一些简单应用**

1、判断奇偶数

通常我们判断一个数是不是偶数，只需要把该数对2取余判断得到的结果是否为0，如果是为0，则表示该数是偶数，如下的逻辑

if (value % 2 == 0) {
                //偶数
            } else {
                //奇数
            }

但是判断奇偶数还有一种直接通过位运算来实现。一个数转换为二进制之后，其实奇数或者是偶数是由最后一位确定的，最后一位为0，则表示是偶数，最后一位为1，则表示是奇数。所以问题就转换为判断转换之后的二进制数的最后一位是 0 还是 1。可以通过下面的代码进行说明。

// 1 转换为二进制的后4位是0001，前面的几位全是0,
    if ((value & 1) == 0) {
           //偶数
        } else {
           //奇数
        }

2、判断第n位是否为1

其实判断第n为是否为1，也比较简单，前面判断奇偶性时其实就是判断第 1 位是否为1

if ((x & (1 << n-1)) == 0) {
        // 第 n 位设置为 0
    }
    else {
        // 第 n 位设置为 1
    }

解释如下：以 x = 5 ， n = 3 进行说明，记得移动的是 n - 1 位。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_18_color_FFFFFF_t_70_g_se_x_16][]

3、 将第 n 位设置为 1

上面解释过，或 运算符，当有一个为 1 时 结果为1，所以我们要把 第 n 位设置为 1，可以通过如下逻辑进行

x = x | (1 << n - 1);

4、将第 n 位设置为 0

与（&）运算符，当两位都为 1 时结果为 1 ，否则结果为 0，可以通过下面的逻辑进行

// 1 << n - 1,表示把 1 左移 n - 1位，取反表示除了第 n 位，其他位都为 1 
    x = x & ~(1 << n - 1);

5、将第 n 位的值取反，也就是 1 变为 0 ，0 变为 1

根据 异或 （**^**）的逻辑，相同则为 0 ，不同则为 1，那 其实我们可以通过下面的逻辑进行

x = x ^ (1 << n - 1);

举个例子进行说明

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_14_color_FFFFFF_t_70_g_se_x_16 1][]

如上图，根据异或的规则，如果参与运算的两位相同，则结果为 0 ，不同，则结果为 1 ，所以对于第 n 为，1 << n - 1 之后已经是 1 了，如果原始数据中第 n 为是 1，则相同了，值变为0，如果值为 0 ，不同了，则变为 1，从而实现 第 n 位的值取反，对于其他位，1 << n - 1 位之后，其他位全部为 0 ，原始数据中，对应位为 0，则为 0，对应位为 1 则结果为 1 。

6、几个运算

x & x == x
    x ^ x == 0  //这个特性判断重复的数字时有用
    x | x == x

7、将最右边的 1 设为 0

y = x & (x-1)

下面结合图解释下

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_18_color_FFFFFF_t_70_g_se_x_16 1][]

**下面结合几个题来进行说明**

1、Leetcode(136) 只出现一次的数字

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。根据异或运算符的特性，有如下

0 ^ x ==  x
    x ^ x ==  0

由于除了某一个数只出现一次之外，其他数都出现两次，代码如下

public int singleNumber(int[] nums) {
            int result = 0;
            for (int i = 0; i < nums.length; i++) {
                result = result ^ nums[i];
            }
            return result;
        }

1、Leetcode(137) 只出现一次的数字II

给你一个整数数组 `nums` ，除某个元素仅出现 **一次** 外，其余每个元素都恰出现 **三次 。**请你找出并返回那个只出现了一次的元素

**解法一、**这个题目最直观的解法就是，定义一个Map，统计每个元素出现的次数，最后仅出现一次的元素即为待求解的结果。

public int singleNumber(int[] nums) {
             HashMap<Integer, Integer> map = new HashMap();
            for (int num : nums) {
                map.put(num, map.getOrDefault(num, 0) + 1);
            }
    
            for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
                if (entry.getValue() == 1) return entry.getKey();
            }
            return 1;
        }

**解法二、**利用位运算符来解决这个问题

数组中元素都在int（4个字节，32位）的范围内，假设我们定义答案为ans（也是4个字节，32位），则ans的每一位的计算逻辑其实可以根据题目的描述推理出，从题目的描述中我们可知，除了一个元素出现一次之外，其余的元素都出现三次，可以结合下图看看。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_20_color_FFFFFF_t_70_g_se_x_16][]

如上图所示，假如出现三次的元素分别为**元素A ... 元素B，**出现一次的元素为**元素Ｓ**，假设我们要计算第ｎ位的值时，我们可以得出，出现三次的那些元素第ｎ位的和要么是０，要么是３的倍数，（1）记出现三次的第ｎ位的和为 sum3

（2）记出现一次的第 n 位 为 sum1。

那 (sum1 + sum3) % 3 取余之后得到的值即为结果中第n位的值。经上面分析，代码如下：

public int singleNumber(int[] nums) {
            int ans = 0;
            for (int i = 0; i < 32; ++i) {
                int total = 0;
                for (int num : nums) {
                    //num向右移i位再与1求&，就可以判断第i位是0还是1,。
                    total += ((num >> i) & 1);
                }
                if (total % 3 != 0) {
                    //把第i为设置为1.
                    ans |= (1 << i);
                }
            }
            return ans;
        }

更多骚操作，可参考末尾链接大牛的文章，特别是用位来实现N皇后的问题很赞。

[https://mp.weixin.qq.com/s/45mfS3ciiVt8nghUSjezFg][https_mp.weixin.qq.com_s_45mfS3ciiVt8nghUSjezFg]

[20210907185929245.png]: /images/20220829/8f3592431f03483983541067b9d55370.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_12_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/505ef6f2602143ac9f90bea4f5133477.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_15_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/638c87b89d084fc580c5788be2316a0b.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_14_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/a14fc0426fb74b2bbe402543af8c1f4a.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_18_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/8951add8193045518acfdf624de0824c.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_14_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220829/8962791c32c3433d8f63eeba2eebf510.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_18_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220829/338efa260da54c9cb5107a6e5b37a20e.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/db67aa28e09e4cfca1f349f8a611bb7b.png
[https_mp.weixin.qq.com_s_45mfS3ciiVt8nghUSjezFg]: https://mp.weixin.qq.com/s/45mfS3ciiVt8nghUSjezFg