Brian Kernighan's 算法

介绍

Brian Kernighan's 算法是一种用于计算一个整数的二进制表示中有多少个1的高效算法。该算法的基本思想是每次将该整数的最右边的一个1置为0，直到该整数变为0为止。每次将1置为0的操作都会使得该整数的二进制表示中的1的个数减少1。

int count_set_bits(int n) {
    int count = 0;
    while (n) {
        n &= (n - 1);
        count++;
    }
    return count;
}

时间复杂度为 \(O(k)\)，\(k\) 为 \(n\) 的二进制表示中1的个数。

例题

蓝桥杯.最少的1
给定正整数n,它的二进制的1的个数有多少？

输入格式：
输入一行包含一个整数 n
输出格式：
输出一行包含一个整数表示答案。
样例输入
7
样例输出
3

代码:

#include <iostream>
using namespace std;
// 计算整数n的二进制表示中1的个数
int count_set_bits(int n) {
    int count = 0;
    while (n) {
        n &= (n - 1);
        count++;
    }
    return count;
}

// 计算n的所有倍数的二进制表示中1的最少个数
int min_set_bits_multiple(int n, int k) {
    int min_set_bits = count_set_bits(n);
    for (int i = 2; i <= k; i++) {
        int set_bits = count_set_bits(i * n);
        if (set_bits < min_set_bits) {
            min_set_bits = set_bits;
        }
    }
    return min_set_bits;
}

int main()
{
  // 请在此输入您的代码
  int n; 
  cin >> n;
  cout << min_set_bits_multiple(n, 555);
  return 0;
}

本质上还是暴力破解，但是能通过测评。