简单介绍

lowbit是二进制中比较常用的一个函数，它的作用是求
一个数（二进制下）从后向前数直到遇到第一个’1’时的数
见下表：

具体lowbit函数的代码实现是这个样子的：

int lowbit(int x) {
return x&-x;//巧妙地运用了补码的特性
}

那如何用lowbit函数求一个数的二进制形式下有多少个’1’呢？
这段的代码也很简易：

int work(int x) {
int num = 0;
while(x) {
x -= lowbit(x);
num++;
}
return num;
}

一些应用

lowbit的应用还是很广泛的

数论

比如一些数论里面的题：luogu p1582倒水

题目描述

一天，CC买了N个容量可以认为是无限大的瓶子，开始时每个瓶子里有1升水。接着~~CC发现瓶子实在太多了，于是他决定保留不超过K个瓶子。每次他选择两个当前含水量相同的瓶子，把一个瓶子的水全部倒进另一个里，然后把空瓶丢弃。(不能丢弃有水的瓶子)

显然在某些情况下CC无法达到目标，比如N=3,K=1。此时CC会重新买一些新的瓶子(新瓶子容量无限，开始时有1升水)，以到达目标。

现在CC想知道，最少需要买多少新瓶子才能达到目标呢？

输入输出格式

输入格式：
一行两个正整数， N,K(1le Nle 2times 10^9,Kle 10001≤N≤2×10
9
,K≤1000 )。

输出格式：
一个非负整数，表示最少需要买多少新瓶子。

十分巧妙的运用了lowbit
Ac代码：

#include<iostream>
#include<cstdio>
using namespace std;
int n, k, ans;
int lowbit(int x) { return x&-x; }
int work(int x) {
int num = 0;
while(x) {
x -= lowbit(x);
num++;
}
return num;
}
int main() {
scanf("%d%d", &n, &k);
while(work(n) > k) ans += lowbit(n), n += lowbit(n);
printf("%dn", ans);
}

树状数组

说到lowbit最著名的应用就是树状数组了
nlogn的复杂度秀一脸…

树状数组的模板：

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define For(i, l, r) for(int i = l; i <= r; ++i)
int n, m, a[500001], tree[500001];
int lowbit(int x) {
return x & -x;
}
int Query(int x) {
int ans = 0;
while(x) {
ans += tree[x];
x -= lowbit(x);
}
return ans;
}
int Ask(int l, int r) {
return Query(r) - Query(l - 1);
}
void Update(int x, int y) {
while(x <= n) {
tree[x] += y;
x += lowbit(x);
}
}
int main() {
scanf("%d%d", &n, &m);
For(i, 1, n) {
scanf("%d", &a[i]);
Update(i, a[i]);
}
For(i, 1, m) {
int x, y, a;
scanf("%d%d%d", &a, &x, &y);
if(a == 1) Update(x, y);
else printf("%dn", Ask(x, y));
}
}

题目链接：戳

最后

以上就是含糊龙猫为你收集整理的关于lowbit简单介绍一些应用的全部内容，希望文章能够帮你解决关于lowbit简单介绍一些应用所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。