长安网站建设定制,wordpress jenn 主题,当当网网站建设,企业网站建设好的案例一.位运算总结:
在解题之前理解一下为什么需要位运算#xff1f;它的本质是什么#xff1f;
力扣上不少位运算相关的题#xff0c;并且很多题也会用到位运算的技巧。这又是为什么#xff1f;
位运算的由来 在计算机里面#xff0c;任何数据最终都是用数字来表示的…一.位运算总结:
在解题之前理解一下为什么需要位运算它的本质是什么
力扣上不少位运算相关的题并且很多题也会用到位运算的技巧。这又是为什么
位运算的由来 在计算机里面任何数据最终都是用数字来表示的不管是我们平时用的软件看的图片视频还是文字。 并且计算机运算单元只认识高低电位转化成我们认识的逻辑也就是 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位置为1x | (1 n) 仅将第n位置为0x (~(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 count0;while(n){if(n%21)count;n/2;}return count;
}
