---
title: "lowbit(x)"
created: 2025-11-28
tags:
  - 算法
---

# lowbit(x)

## 题目 [**二进制中1的个数**](https://www.acwing.com/problem/content/803/)

![[image-0504afbe.png]]

## 思路分析

返回x的最后一位1

内部实现很简单

int lowbit(x){

return x&-x;

}

这个x&-x等价于 x&(~x+1)

假设

x=1010……1000……

~x=0101……0111……

~x+1=0101……1000……

将x&(~x+1)得0000……1000……

也就是只保留从右边数第一个1 其他全变成了0

然后就可以利用这个性质 求某二进制序列中有多少个1（一直循环直到没有就行了）

`int x; cin>>x;`

`int res=0;`

`while(x){ x-=lowbit(x); res++;}`

如此可得x中1的个数

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

//const int N=100010;

//int q[N];

int lowbit(int x)

{

    return x&-x;

}

int main()

{

    int n;

    cin>>n;

    while(n--)

    {

        //无需多此一举存入数组 读入一个数就立即对它操作就好了

        int x;

        cin>>x;

        int res=0;

        while(x)

        {

            x-=lowbit(x);

            res++;

        }

        cout<<res<<" ";

    }

    return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[n--k&1|n--k&1]] 🏠 [[00-听课板子]] ➡️ [[2-Learning/02-算法/02-听课板子/基础算法/离散化|离散化]]