What does the following Python function compute for a positive integer n?
def mystery(n):
count = 0
while n > 0:
count += n & 1
n >>= 1
return count
Answer and explanation
Correct answer: C. The number of set bits (1s) in the binary representation of n
- Step 1: Examine bitwise operations: `n & 1` checks the least significant bit (1 if odd, 0 if even).
- Step 2: `n >>= 1` shifts the bits right by one position on each iteration. Summing `n & 1` counts all 1s (set bits/Hamming weight) in the binary representation of .
Answer
The number of set bits (1s) in the binary representation of n.
Why not the others: Decimal digit sums require `% 10` and `// 10`; prime factors and square roots require arithmetic factoring routines.
Practise more Algorithms and Python Programming.
Free questions with an explanation for every one, and full timed EmSAT Achieve (UAE) mock tests.
More Algorithms and Python Programming questions
- What is the output of the following Python expression: [x**2 for x in range(6) if x % 2 != 0]?
- What is the worst-case time complexity of searching for an element in a balanced binary search tree (AVL tree) containing n nodes?
- What will be printed by the following Python code snippet?
def func(val, lst=[]):
lst.append(val)
return lst
print(func(1))
print(… - Which abstract data structure operates on a First-In, First-Out (FIFO) ordering principle?
- What is the return value of executing the recursive Python function `mystery(4)`?
def mystery(n):
if n <= 1:
return 1
retur… - What is the worst-case time complexity of the standard QuickSort algorithm when the chosen pivot is consistently the smallest or largest ele…