自学内容网 自学内容网

(笔记自用)位运算总结+LeetCode例题:颠倒二进制位+位1的个数

一.位运算总结:

在解题之前理解一下为什么需要位运算?它的本质是什么?

力扣上不少位运算相关的题,并且很多题也会用到位运算的技巧。这又是为什么?

位运算的由来
在计算机里面,任何数据最终都是用数字来表示的(不管是我们平时用的软件,看的图片,视频,还是文字)。
并且计算机运算单元只认识高低电位,转化成我们认识的逻辑,也就是 0 1 。

这就是导致计算机里面任何数据最终都是用二进制(0 1)来保存的数字。只是我们平时看到的图片、文字、软件都只从二进行数字转化而来的。

位运算符:
常用位操作:
1.判断奇偶
        (x & 1) == 1 ---等价---> (x % 2 == 1)
        (x & 1) == 0 ---等价---> (x % 2 == 0)
2.x / 2 ---等价---> x >> 1
3.x &= (x - 1) ------> 把x最低位的二进制1给去掉
4.x & -x -----> 得到最低位的1
5.x & ~x -----> 0
6.指定位置的位运算
        将X最右边的n位清零:x & (~0 << n)
        获取x的第n位值:(x >> n) & 1
        获取x的第n位的幂值:x & (1 << n)
        仅将第n位置为1:x | (1 << n)
        仅将第n位置为0:x & (~(1 << n))
        将x最高位至第n位(含)清零:x & ((1 << n) - 1)
        将第n位至第0位(含)清零:x & (~((1 << (n + 1)) - 1))


7.异或结合律
x ^ 0 = x, x ^ x = 0
x ^ (~0) = ~x, x ^ (~x) = ~0
a ^ b = c, a ^ c = b, b ^ c = a
字母表示:(a ^ b) ^ c = a ^ (b ^ c)
图形表示:(☆ ^ ◇) ^ △ = ☆ ^ (◇ ^ △)

作者:疯子

链接:https://leetcode.cn/problems/reverse-bits/solutions/658732/ccying-gai-zhi-dao-de-wei-cao-zuo-zong-j-etzo/

来源:力扣(LeetCode)

二.Leetcode例题:颠倒二进制位

1.题目:

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

示例 1:

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

示例 2:

输入:n = 11111111111111111111111111111101
输出:3221225471 (10111111111111111111111111111111)
解释:输入的二进制串 11111111111111111111111111111101 表示无符号整数 4294967293,
     因此返回 3221225471 其二进制表示形式为 10111111111111111111111111111111 。

提示:

  • 输入是一个长度为 32 的二进制字符串

2.题解:

每次把 res 左移,把 n 的二进制末尾数字,拼接到结果 res 的末尾。然后把 n 右移。

举一个 8 位的二进制进行说明:

i    n                   res
-    11001001      -
0    1100100       1
1    110010         10
2    11001           100
3    1100             1001
4    110               10010
5    11                 100100
6    1                   1001001
8    -                    10010011


作者:负雪明烛
链接:https://leetcode.cn/problems/reverse-bits/solutions/686503/fu-xue-ming-zhu-xun-huan-yu-fen-zhi-jie-hoakf/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

uint32_t reverseBits(uint32_t n) {
    uint32_t res = 0;
    for (int i = 0; i < 32; ++i)
        res = (res << 1) + (n >> i & 1);
    return res;
}

//注意:n >> i & 1 从n中取出第i位(从右往左数,最右边的是第0位)
//    res << 1 为新计算出的位(从n中取出的那一位)腾出空间。
//    (res << 1) + (n >> i & 1) 如果n的第i位是1,则在result的相应位置上也设置为1;
//                                 如果是0,则保持不变(因为加上0不改变原值)

三.LeetCode例题:位1的个数

1.题目:

编写一个函数,获取一个正整数的二进制形式并返回其二进制表达式中 

设置位

 的个数(也被称为汉明重量)。

示例 1:

输入:n = 11
输出:3
解释:输入的二进制串 1011 中,共有 3 个设置位。

示例 2:

输入:n = 128
输出:1
解释:输入的二进制串 10000000 中,共有 1 个设置位。

示例 3:

输入:n = 2147483645
输出:30
解释:输入的二进制串 11111111111111111111111111111101 中,共有 30 个设置位。

提示:

  • 1 <= n <= 231 - 1

2.题解:

利用上面提到的常用位操作:
x &= (x - 1)
从右往左,每次把最低位的 1 给打掉,并累加被打掉1的次数

如:

n     :    0B101011
n - 1 :   0B101010
------------------
&     :   0B101010


n     :   0B101000
n - 1 :   0B100111
------------------
&     :   0B100000

作者:疯子
链接:https://leetcode.cn/problems/number-of-1-bits/solutions/658783/ying-gai-zhi-dao-de-wei-cao-zuo-zong-jie-idne/
来源:力扣(LeetCode)
 

int hammingWeight(uint32_t n) 
{
    int result = 0;
    while (n ? ++result, (n &= (n - 1)) : 0);
    //若n非0,则每次去掉最低位的1并计数,否则退出循环
    return result;
}

此题也可以用暴力破解,但效率不如使用位运算

int hammingWeight(int n) {
    int count=0;
    while(n)
    {
        if(n%2==1)
            count++;
        n/=2;
    }
    return count;
}


原文地址:https://blog.csdn.net/changan277/article/details/142420091

免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!