关于lowbit的那些事

lowbit是树状数组的前置知识。

lowbit(x)返回的是x的二进制表达式中最低位的1所对应的值。

e.g.

6的二进制是 0000 0110

从右往左数，第一个1出现在第2位上，对应的数是2^1也就是2，因此lowbit(6)=2

24的二进制是 0001 1000

从右往左数，第一个1出现在第4位上，对应的数是2^3也就是8，因此lowbit(24)=8

那么怎么用函数实现呢？

这就扯到了一个特别玄学的东西：补码

相关知识详见这里(戳我)

代码如下：

 1 #include<iostream>
 2 using namespace std;
 3 
 4 int a;
 5 
 6 int lowbit(int x)
 7 {
 8     return (x)&(-x);
 9 }
10 
11 int main()
12 {
13     cin>>a;
14     cout<<lowbit(a);
15     return 0;
16 }

额  (x)&(-x)是个啥？

它就是：将x的补码按位与-x的补码

我们来验证一下：

lowbit(6)就等于()

关于lowbit的那些事

原文：https://www.cnblogs.com/void-null/p/15165866.html