how to use the bit operations to find the number of units with running time O (k)

Question

How to use the bit operations to find the number of units with running time O (k),

k - number of units in binary notation?

    int n, ans;
    cin >> n;
    while (n) {
        if (n & 1) {
            ans++;
        }
        n = (n >> 1);
    }
    cout << ans;

Time complexity of my solution is O(log n). But I need O(k).

@Damien I don't think I get you. 10 is 1010, k = 2 and log n = 4. So k < log n. — Yonlif, Dec 21 '19 at 13:42

score 1 · Accepted Answer · answered Dec 21 '19 at 13:22

Number of units in binary notation = Number of set bits.

This is a familiar problem, you are looking for the Brian Kernighan’s Algorithm.

This algorithm works in O(log N), but also in O(K). In every iteration of the algorithm we unset the rightmost bit by performing n & (n - 1), therefore after K iterations the number will be 0 and we are done.

So time complexity is number of units (number of set bits), which is K.

how to use the bit operations to find the number of units with running time O (k)

1 Answers1