☘前言☘
今天是算法零基础打卡的第49天，今天发现个大坑，图片之前没改日期，失误失误-.-开始学习。上链接：
《算法零基础100讲》(第49讲) 位运算 (右移)
🧑🏻作者简介：一个从工业设计改行学嵌入式的年轻人
✨联系方式：2201891280(QQ)
⏳全文大约阅读时间： 20min
全文目录
☘前言☘
🎁主要知识点
✨右移
📓二进制形态
📓执行结果
✨右移的应用
📓1.去掉低k位
📓2.取低位连续1
📓3.取第k位的值
📓课后习题
191. 位1的个数
231. 2 的幂
342. 4的幂
405. 数字转换为十六进制数
📑写在最后
🎁主要知识点
✨右移
📓二进制形态
x>>y就是把x右移y位 看下面更好理解。
上面就是对87右移3位的结果
📓执行结果
执行结果其实等价于
其中最外围符号代表向下取整。上一条的87/2^3的结果就是10.
✨右移的应用
📓1.去掉低k位
直接运用右移完成。
📓2.取低位连续1
将原数字+1
将原本的数字和新得到的数字异或
将得到结果>>1即可
(x^(x+1)) >>1
📓3.取第k位的值
(x>>k) &1
📓课后习题
191. 位1的个数
191. 位1的个数
编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量）。
解题思路
利用与运算判断最低位是否为1，然后右移一位直到为0.
int hammingWeight(uint32_t n) { int count = 0; while(n){ if(n & 1) count++; /统计低位1的个数 n>>=1; } return count; }
231. 2 的幂
231. 2 的幂
给你一个整数n，请你判断该整数是否是2的幂次方。如果是，返回 true ；否则，返回false。
如果存在一个整数 x 使得 n == 2x ，则认为 n 是 2 的幂次方。
解题思路
如果最低位是0就右移，看最后的结果是不是1就好了。
bool isPowerOfTwo(int n){ if(n <= 0) return false; while(!(n & 1)) //是0就一直右移 n >>= 1; return n == 1; }
342. 4的幂
342. 4的幂
给定一个整数，写一个函数来判断它是否是 4 的幂次方。如果是，返回true；否则，返回 false 。
整数 n 是 4 的幂次方需满足：存在整数x使得 n == 4x
解题思路
和上面差不多，区别是判断条件是3(11)的与结果为0.
bool isPowerOfFour(int n){ if(n <= 0) return false; while(!(n & 3)) n >>= 2; return n == 1; }
405. 数字转换为十六进制数
405. 数字转换为十六进制数
给定一个整数，编写一个算法将这个数转换为十六进制数。对于负整数，我们通常使用 补码运算方法。
解题思路
其实就是四位一组处理一下就好了。然后我们处理的时候是从低位开始的，但是打印的时候要从高位开始，所以用一下栈。
char * toHex(int num){ char s[16] = {'0','1','2','3','4','5','6','7','8','9','a','b','c','d','e','f'}; char *ans = malloc(sizeof(char) * 9); int count = 0,stack[8],countnum = 0; if(num == 0) ans[count++] = '0'; //0的特殊判定 unsigned int a = num; while(a){ //每四位一组写入栈 stack[countnum++] = a % 16; a >>= 4; } while(countnum){ //出栈写入结果 ans[count++] = s[stack[--countnum]]; } ans[count] = 0; return ans; }
