Neovim-如何使用编辑器的神

二进制中1的个数

https://www.acwing.com/problem/content/description/803/

https://leetcode.cn/problems/number-of-1-bits/

时间复杂度是$O(nlogn)$, 其中$n$是二进制位数.

注意, 这个方法对于负数同样适用.

#include <iostream>

using namespace std;

const int N = 100010;

int n;
int a[N];

/* 统计x二进制表示中1的个数 */
int count(int x) {

    int cnt = 0;
    while (x) {
        x -= x & -x;
        cnt ++;
    }
    return cnt;
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) cout << count(a[i]) << ' ';

    return 0;
}

对齐地址

这不是一个算法题, 一般系统有这样一个要求, 给定一个地址addr, 要求这个地址按照n字节对齐 (这个n一般是2的整数次幂), 然后返回对齐后的地址.

假设n = 2^k, 那么可以用如下函数求:

static inline uint32_t align(uint32_t addr, int n) {
  return (addr + n - 1) & ~(n - 1);
}

证明:

• 首先证明: a & ~(n - 1) = a - a % n
  • 首先, n-1一定是有log(n)个全1, 前面是全0, 一取反就是前面全是1, 后面log(n)是全0, 然后一取与, 就把a的后面log(n)位全变成0, 前面位保留.
  • a % n的结果就是a的二进制表示后面log(n)位, 然后再用a一减, 效果等价.
• 因此, (addr + n - 1) & ~(n - 1) = addr + n - 1 - (addr + n - 1) % (n - 1) = addr + (n - 1) - addr % (n - 1), 最终得到的表达式本质上就是返回后的地址.