Primitive Types

Prev: Problem Solving Patterns Next: Arrays

Problems

5.1

The parity of a binary word is 1 if the number of 1s in the word is odd; otherwise, it is 0. For example, the parity of $1011$ is 1, and the parity of $10001000$ is 0. Parity checks are used to detect single-bit errors in data storage and communication.

How would you compute the parity of a very large number of 64-bit words?

Hint: Use a lookup table, but do not use $2^{64}$ entries.

5.2

A 64-bit integer can be viewed as an array of 64 bits, with bit 0 the least significant bit and bit 63 the most significant bit.

Implement code that takes as input a 64-bit integer and swaps the bits at indices $i$ and $j$ .

Hint: When is the swap actually necessary?

5.3

Write a program that takes a 64-bit word and returns the 64-bit word consisting of the bits of the input word in reverse order. For example, if the input is alternating 1s and 0s, $(1010 \dots 10)$ , the output should be alternating 0s and 1s, $(0101 \dots 01)$ .

Hint: Use a lookup table.

5.4

Define the weight of a nonnegative integer $x$ to be the number of bits set to 1 in its binary representation. For example, since $92$ is $(1011100)_{2}$ , its weight is 4.

Write a program which takes as input a nonnegative integer $x$ and returns a number $y$ such that $y \neq = x$ , $y$ has the same weight as $x$ , and $∣ y - x ∣$ is as small as possible. You may assume $x$ is neither 0 nor all 1s. For example, if $x = 6$ , you should return $5$ .

Hint: Start with the least significant bit.

Variant: Solve the same problem in $O (1)$ time and space.

5.5

Sometimes processors used in ultra-low-power devices do not have dedicated hardware for multiplication. A program that needs multiplication must then do it explicitly using lower-level primitives.

Write a program that multiplies two nonnegative integers. The only operations you are allowed to use are:

assignment
the bitwise operators $>>$ , $<<$ , $∣$ , $&$ , $\sim$ , $^{\land}$
equality checks and Boolean combinations thereof

You may use loops and functions that you write yourself. In particular, you may not use increment, decrement, or order comparisons such as $x < y$ .

Hint: Add using bitwise operations; multiply using shift-and-add.

5.6

Given two positive integers, compute their quotient using only the addition, subtraction, and shifting operators.

Hint: Relate $x / y$ to $(x - y) / y$ .

5.7

Write a program that takes a double $x$ and an integer $y$ and returns $x^{y}$ . You may ignore overflow and underflow.

Hint: Exploit mathematical properties of exponentiation.

5.8

Write a program which takes an integer and returns the integer corresponding to the digits of the input written in reverse order. For example, the reverse of $42$ is $24$ , and the reverse of $- 314$ is $- 413$ .

Hint: How would you solve the same problem if the input were presented as a string?

5.9

A palindromic string reads the same forwards and backwards. In this problem, determine whether the decimal representation of an integer is a palindrome. For example, the answer should be true for $0$ , $1$ , $7$ , $11$ , $121$ , $333$ , and $2147447412$ , and false for $- 1$ , $12$ , $100$ , and $2147483647$ .

Write a program that takes an integer and determines whether its decimal representation is a palindrome.

Hint: It is easy to extract the least significant digit. Can you find a simple expression for the most significant digit?

5.10

Six friends need to select a designated driver using a single unbiased coin, and the process should be fair to everyone.

How would you implement a random number generator that generates a random integer $i$ between $a$ and $b$ , inclusive, given a random number generator that produces 0 or 1 with equal probability? All values in $[a, b]$ should be equally likely.

Hint: How would you mimic a three-sided coin with a two-sided coin?

5.11

This problem concerns rectangles whose sides are parallel to the X-axis and Y-axis.

Write a program which tests if two rectangles have a nonempty intersection. If the intersection is nonempty, return the rectangle formed by their intersection.

Hint: Think of the X and Y dimensions independently.

Variant: Given four points in the plane, how would you check if they are the vertices of a rectangle?

Variant: How would you check if two rectangles, not necessarily aligned with the X and Y axes, intersect?

Answers

5.1

For a single word, parity can be computed by examining one bit at a time and XORing the low bit into an accumulator. That gives $O (n)$ time for an $n$ -bit word, or $O (k)$ if you repeatedly clear the lowest set bit with $x & = x - 1$ , where $k$ is the number of set bits.

For many parity computations, cache the parity of all 16-bit values, split a 64-bit word into four 16-bit chunks, and XOR the four cached parities. This gives $O (n / L)$ time with $L$ -bit table keys, plus table initialization. Another standard improvement is XOR folding: repeatedly XOR the word with itself shifted by 32, 16, 8, 4, 2, and 1 bits, then read the low bit. That gives $O (lo g n)$ time.

5.2

If the bits at $i$ and $j$ are equal, do nothing. If they differ, flip both with a mask that has 1s only at those positions:

x ^= (1UL << i) | (1UL << j)

This is $O (1)$ .

5.3

For a one-off reversal, swap bit $k$ with bit $63 - k$ for $k = 0..31$ . For repeated use, precompute the reversal of every 16-bit value, split the 64-bit input into four 16-bit chunks, reverse each chunk with the lookup table, and place them back in the opposite order.

That yields the reversed word in $O (n / L)$ time for $L$ -bit table entries, with $L = 16$ in the book’s solution.

5.4

The closest number with the same weight is obtained by swapping the two rightmost consecutive bits that differ. Scanning from the least significant end guarantees the smallest possible change in value.

This takes $O (n)$ time in the word size. The chapter also gives the $O (1)$ -space variant prompt, but the main idea is still to find the lowest differing adjacent pair and swap it.

5.5

Use grade-school shift-and-add multiplication in binary. Iterate through the bits of one operand; whenever the current bit of $x$ is 1, add the current value of $y$ into the running total, then shift $x$ right and $y$ left.

The only nontrivial subroutine is addition. Implement that bit-by-bit with XOR for the sum bit and carry propagation for the carry bit, i.e. a ripple-carry adder built from bitwise operations. If $n$ is the operand width, addition is $O (n)$ and multiplication is $O (n^{2})$ .

5.6

Repeated subtraction is too slow. Instead, repeatedly subtract the largest power-of-two multiple of $y$ that does not exceed the current $x$ , and add the same power of two to the quotient.

In practice, shift $y$ left until it would exceed $x$ , back off one step, subtract that value, and continue. This is the binary analogue of long division and runs in $O (n)$ time when word operations are $O (1)$ .

5.7

Use exponentiation by squaring. If $y$ is negative, replace $x$ by $1/ x$ and $y$ by $- y$ . Then repeatedly:

if the low bit of $y$ is 1, multiply the result by $x$
square $x$
shift $y$ right by 1

This uses $O (lo g ∣ y ∣)$ multiplications.

5.8

Avoid converting to a string. Record the sign, work with $∣ x ∣$ , and repeatedly build the answer with:

result = result * 10 + x_remaining % 10
x_remaining /= 10

Apply the original sign at the end. If the input has $d$ digits, the running time is $O (d)$ .

5.9

Negative inputs are immediately false. Otherwise, compare the most significant digit and least significant digit, then remove both and continue inward.

The low digit is $x mod 10$ . If $n$ is the number of digits, the high digit is $x /1 0^{n - 1}$ . After comparing them, drop the high digit with modulo and the low digit with division by 10, and shrink the leading-power mask by a factor of 100. This uses $O (d)$ time and $O (1)$ space.

5.10

Let $t = b - a + 1$ . Generate enough fair bits to produce a number in $[0, 2^{k} - 1]$ , where $2^{k} \geq t$ and $k$ is minimal. If the sampled value is less than $t$ , return $a + value$ ; otherwise, reject it and try again.

This is rejection sampling. Each trial uses $O (lo g (b - a + 1))$ calls to the 0/1 generator, and the expected number of trials is constant, so the expected running time is $O (lo g (b - a + 1))$ .

5.11

Two axis-aligned rectangles intersect iff their projections overlap on both axes. If one rectangle lies entirely to the left, right, above, or below the other, there is no intersection.

When they do intersect, the intersection rectangle is:

left edge: $max (r_{1} . x, r_{2} . x)$
bottom edge: $max (r_{1} . y, r_{2} . y)$
right edge: $min (r_{1} . x + r_{1} . width, r_{2} . x + r_{2} . width)$
top edge: $min (r_{1} . y + r_{1} . height, r_{2} . y + r_{2} . height)$

This is $O (1)$ .

Takashi's Notes

Explorer

Primitive Types

Primitive Types

Problems

5.1

5.2

5.3

5.4

5.5

5.6

5.7

5.8

5.9

5.10

5.11

Answers

5.1

5.2

5.3

5.4

5.5

5.6

5.7

5.8

5.9

5.10

5.11

Graph View

Table of Contents

Backlinks