English
Menu

Programming Basics (Pseudocode Tracing)

∧ is bitwise AND. What is the value of c after the following program runs?

integer: x ← 200, c ← 0
while (x ≠ 0)
  x ← x ∧ (x − 1)
  c ← c + 1
endwhile
  1. A3
  2. B5
  3. C8
Show answer and explanation

Answer: A. 3

The bitwise operation x ∧ (x − 1) clears the lowest 1 bit of x. In x − 1 the lowest 1 becomes 0 and all the 0s below it become 1, so the AND clears just that part. 200 = 11001000 becomes 11000000 = 192, then 10000000 = 128, then 0, so the loop runs 3 times. c ends up as the number of 1 bits in the binary form of x.

  • A. Correct. 200 = 11001000 has three 1 bits.
  • B. This is the number of 0 bits. The program clears the 1 bits one at a time.
  • C. This is the 8-bit width. The loop runs once per 1 bit.
Practice this topic Back to topic

Related calculators

Pseudocode Runner and TracerRun programs written in the pseudocode of Japan's Fundamental IT Engineer Exam (Part B) and trace each executed line and the values of variablesBitwise Operations CalculatorCheck AND, OR, XOR, NOT and logical shifts, arithmetic shifts and rotations as rows of binary bits, for 8 to 64 bits

Books on Programming Basics (Pseudocode Tracing) Ad

As an Amazon Associate I earn from qualifying purchases.

More Programming Basics (Pseudocode Tracing) questions

  1. x and y are 8-bit unsigned integers. << and >> are logical shifts: vacated bits are filled with 0, and bits shifted out of the 8 bits are discarded. ∨ is bitwise OR. With x = 75, what is the value of y after the following assignment?
  2. The following procedure bubble is a bubble sort that sorts the integer array data in ascending order. swap(data, j, k) is a procedure that swaps the values of data[j] and data[k]. Array indices start at 1. What should replace 【a】 in the program?
  3. ÷ is division; when the result is assigned to an integer variable (including a function argument), the fractional part is discarded. The following program finds in lo the index of the first value that is at least x in the integer array data, which is sorted in ascending order (indices start at 1). x is no greater than the last element of data. What should replace 【a】 in the program?
  4. A stack is represented by the 5-element integer array st and the integer variable top. All elements of st start at 0 and top starts at 0. push(v) adds 1 to top and then does st[top] ← v; pop() returns the value of st[top] and then subtracts 1 from top (the elements of st are not changed). What are top and st after the following program runs?
  5. A queue uses the 4-element string array q as a ring. head and tail start at 1. enq(v) does q[tail] ← v and then tail ← tail mod 4 + 1; deq() returns the value of q[head] and then does head ← head mod 4 + 1. When the following program runs, in which element of q is "E" stored?