Count Set Bits Brian Kernighan Algorithm in DSA C - Cheat Sheet & Quick Revision

Recall & Review

beginner

What does the Brian Kernighan algorithm count in a number?

It counts the number of set bits (1s) in the binary representation of the number.

intermediate

How does the Brian Kernighan algorithm reduce the number of operations compared to checking each bit?

It repeatedly clears the rightmost set bit, reducing the number of iterations to the number of set bits instead of total bits.

intermediate

Explain the operation 'n = n & (n - 1)' in the Brian Kernighan algorithm.

This operation clears the rightmost set bit of n by turning it to 0, effectively reducing the count of set bits by one.

intermediate

What is the time complexity of the Brian Kernighan algorithm for counting set bits?

O(k), where k is the number of set bits in the number, making it efficient for sparse bit patterns.

beginner

Write the basic C code snippet for counting set bits using Brian Kernighan's algorithm.

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

What does the expression 'n & (n - 1)' do in Brian Kernighan's algorithm?

A Clears the rightmost set bit of n

B Sets the rightmost unset bit of n

C Inverts all bits of n

D Shifts n to the right by one bit

The expression 'n & (n - 1)' clears the rightmost set bit in n, which is the key step in Brian Kernighan's algorithm.

What is the main advantage of Brian Kernighan's algorithm over checking each bit individually?

A It counts unset bits instead of set bits

B It uses less memory

C It works only for positive numbers

D It runs in time proportional to the number of set bits, not total bits

Brian Kernighan's algorithm runs in O(k) time where k is the number of set bits, making it faster than checking all bits.

If a number has 5 set bits, how many times will the loop run in Brian Kernighan's algorithm?

A Number of total bits in the number

B 5

C Depends on the number's value

D Always 1

The loop runs exactly as many times as there are set bits, so 5 times for 5 set bits.

What initial value should the count variable have in the Brian Kernighan algorithm?

A Number of bits in the integer

B 1

C 0

D Undefined

Count starts at 0 and increments each time a set bit is cleared.

Which of these is a correct output of countSetBits(13) using Brian Kernighan's algorithm?

A 3

B 4

C 2

D 5

13 in binary is 1101, which has 3 set bits.

Describe how Brian Kernighan's algorithm counts the set bits in an integer.

Think about how the number changes each loop iteration.

Explain why Brian Kernighan's algorithm is more efficient than checking each bit one by one.

Consider the number of loop iterations.