05.md

Cracking the Coding Interview: 6th Edition (in C++)

Return to README

See also: Completed Question List

Chapter 05 | Bit Manipulation

5.1: Insertion ./ctci6 05 01

• You are given two 32-bit numbers, N and M, and two bit positions, i and j.
  Write a method to insert M into N such that M starts at bit j and ends at bit i.

  You can assume that the bits j through i have enough space to fit all of M.

  That is, if M = 10011,
  you can assume that there are at least 5 bits between j and i.

  You would not, for example, have j = 3 and i = 2,
  because M could not fully fit between bit 3 and bit 2.

  • EXAMPLE
    

    Input:  N = 10000000000, M = 10011, i = 2, j = 6
    Output: N = 10001001100
    

  • main.cpp
  • header.hpp
  • source.cpp

5.2: Binary to String ./ctci6 05 02

• Given a real number between 0 and 1 (e.g., 0.72) that is passed in as a double, print the binary representation. If the number cannot be represented accurately in binary with at most 32 characters, print "ERROR".
  • main.cpp
  • header.hpp
  • source.cpp

5.3: Flip Bit to Win ./ctci6 05 03

• You have an integer and you can flip exactly one bit from a 0 to a 1.
  Write code to find the length of the longest sequence of 1's you could create.
  • EXAMPLE
    

    Input:      1775    (or: 11011101111)
    Output:     8
    

  • main.cpp
  • header.hpp
  • source.cpp

5.4: Next Number ./ctci6 05 04

• Given a positive integer, print the next smallest and the next largest number that have the same number of 1 bits in their binary representation.
  • main.cpp
  • header.hpp
  • source.cpp

5.5: Debugger ./ctci6 05 05

• Explain what the following code does: ((n & (n - 1)) == 0)
  • main.cpp
  • header.hpp
  • source.cpp

5.6: Conversion ./ctci6 05 06

• Write a function to determine the number of bits you would need to flip to convert integer A to integer B.
  • EXAMPLE
    

    Input:      29 (or: 11101), 15 (or: 01111)
    Output:     2
    

  • main.cpp
  • header.hpp
  • source.cpp

5.7: Pairwise Swap ./ctci6 05 07

• Write a program to swap off and even bits in an integer with as few instructions as possible (e.g. bit 0 and bit 1 are swapped, bit 2 and bit 3 are swapped, and so on).
  • main.cpp
  • header.hpp
  • source.cpp

5.8: Draw Line ./ctci6 05 08)

• A monochrome screen is stored as singly array of bytes, allowing eight consecutive pixels to be stored in one byte.

  The screen has width w, where w is divisible by 8 (that is, no byte will be split across rows). The height of the screen, of course, can be derived from the length of the array and the width.

  Implement a function that draws a horizontal line from (x1, y) to (x2, y)

  The method signature should look something like:
  drawLine(byte[] screen, int width, int x1, int x2, int y)

  • main.cpp
  • header.hpp
  • source.cpp

Return to README

See also: Completed Question List