【漫步刷题路】-位运算x&(-x)的妙用

【漫步刷题路】-位运算x&(-x)的妙用

目录

• • • 前言：
    • x&(-x)总结
    • • 用途：
      • 样例图解
    • 样例1 x&(-x)的运用
    • 例子2 - 求偶数中比特位为1所在的位置

前言：

写文宗旨：坚持每天学习一点知识，勿以题易而弃之，每天坚持“水”文章！

---

---

x&(-x)总结

• 当x为奇数时：结果为1
• 当x为0时 ：结果为0
• 当x为偶数时：得到的是能整除这个偶数的最大的二次幂
• **当x为2的幂次方时候(偶数)-> 则x&(-x) == x 得到的能整除这个偶数的最大的二次幂就算本身 **

---

用途：

1.可用于获取某个二进制数的最低位1所对应的值

2.求一个偶数能被整除的最大的二次幂

---

样例图解

---

样例1 x&(-x)的运用

#include
int main()
{
	int a = 0;
	//循环输入
	while (scanf("%d", &a) != EOF)
	{
		int ret = 0;
		ret = a & (-a);
		if (ret == 1)
		{
			printf("x为奇数n");
		}
		else if (ret == 0)
		{
			printf("x为0n");
		}
		else
			printf("能整除x的最大二次幂为:%dn", ret);
	}
	return 0;
}

---

例子2 - 求偶数中比特位为1所在的位置

int main()
{
	int a = 0;
	int flag = 0;
	printf("请输入一个偶数n");
	scanf("%d", &a);
    flag = a & (-a);
	printf("能整除a的最大的二次幂为：%dn", flag);
	int k = 0;
	while (flag)
	{
		flag  >>= 1;
		k++;
	}
	printf("a中二进制序列最低位为1的是第%d位n", k);
}

因为x&(-x)：当x是偶数时，得到的是能整除这个偶数的最大的二次幂，而2的次方幂对应的二进制只有一个比特位为1.

只需不断把x&(-x)得到的值对应的比特位右移，使用一个变量记录，最后变成全0系列，就可以知道x最低比特位1的是哪一位

---