题目描述

求一个数二进制中1的个数

输入样例

5
1 2 3 4 5

输出样例

1 1 2 1 2

算法1

(右移1位看最末位是否为1，为1就++) $O(n)$

时间复杂度 O(n);

Java 代码

import java.io.*;

class Main {
    static int N = 100010;
    static int[] a = new int[N];
    public static void main (String[] args) throws IOException {
        BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter output = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(input.readLine());
        String[] arr = input.readLine().split("\\s+");
        int count = 0;
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(arr[i]);
            while (a[i] > 0) {
                if ((a[i] & 1) == 1) count++;
                a[i] >>= 1;
            }
            output.write(count + " ");
            count = 0;
        }
        output.flush();
    }
}

算法2

(利用lowbit性质) $O(n/2)$

每次让这个数减去lowbit的值（即减掉一个二进制中的1）并使得结果++，减到就计算出了二进制中1的个数

时间复杂度 O(n/2)

Java 代码

import java.io.*;

class Main {
    static int N = 100010;
    static int[] a = new int[N];
    public static void main (String[] args) throws IOException {
        BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter output = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(input.readLine());
        String[] arr = input.readLine().split("\\s+");
        int count = 0;
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(arr[i]);
            while (a[i] > 0) {
                a[i] -= lowBit(a[i]);
                count++;
            }
            output.write(count + " ");
            count = 0;
        }
        output.flush();
    }

    static int lowBit(int x) {
        return x & (-x);
    }
}