Bit masks and popcount

Questions 1 to 5 of 8

1. 1. Predict the output of this program. ``cpp #include <iostream> using namespace std; int main() { unsigned x = 0b1011; cout << (x & (1u << 1)) << ' ' << ((x & (1u << 2)) != 0) << endl; return 0; } ``

   0 02 12 01 0
2. 2. Fill in the blank: the mask with only bit 5 on is written 1u << ___.

   Type your answer.

3. 3. A 32-bit unsigned value has k bits set. In Big-O terms, how many times does the loop while (n != 0) n &= n - 1; run?

   O(32), a fixed number of stepsO(k), once per set bitO(n), once per unit of the valueO(log n), once per bit position
4. 4. Predict the output of this program. ``cpp #include <iostream> using namespace std; int main() { unsigned n = 40; n &= n - 1; cout << n << ' '; n &= n - 1; cout << n << endl; return 0; } ``

   32 040 3232 168 0
5. 5. Which expression tests whether bit 2 of x is on?

   x & 4 == 4x && 4 == 4(x & 4) != 0x & (4 == 4)