{"id":490,"date":"2013-06-13T23:05:28","date_gmt":"2013-06-14T06:05:28","guid":{"rendered":"http:\/\/192.168.1.2\/wordpress\/?p=490"},"modified":"2013-08-16T16:12:59","modified_gmt":"2013-08-16T23:12:59","slug":"chapter-5-bit-manipulation","status":"publish","type":"post","link":"http:\/\/cywang.no-ip.org\/wordpress\/?p=490","title":{"rendered":"Chapter 5. Bit Manipulation"},"content":{"rendered":"
    \n
  1. \n\t\tYou 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.
    \n\t\tEXAMPLE
    \n\t\tInput:    N = 10000000000, M = 10011, i = 2, j = 6
    \n\t\tOutput: N = 10001001100
    \n\t\t\n\t<\/li>\n
  2. \n\t\tGiven a real number between 0 and 1 (e.g., 0.72) that is passed in as a double, print the binary representation.
    \n\t\tIf the number cannot be represented accurately in binary with less than 32 characters, print “ERRIR.”\n\t<\/li>\n
  3. \n\t\tGiven a positive integer, print the next smallest and the next largest number that have the same number of 1 bits in their binary representation.\n\t<\/li>\n
  4. \n\t\tExplain what the following code does: ( ( n & (n-1) ) == 0).\n\t<\/li>\n
  5. \n\t\tWrite a function to determine the number of bits required to convert integer A to integer B.
    \n\t\tEXAMPLE
    \n\t\tInput: 31, 14
    \n\t\tOutput: 2\n\t<\/li>\n
  6. \n\t\tWrite a program to swap odd 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).\n\t<\/li>\n
  7. \n\t\tAn array A contains all the integers from 0 to n, except for one number which is missing. In this problem, we cannot access an entire integer in A with a single operation.
    \n\t\tThe elements of A are represented in binary, and the only operation we can use to access them is “fetch the j-th bit of A[i],” which takes constant time.
    \n\t\tWrite code to find the missing integer. Can you do it in O(n) time?\n\t<\/li>\n
  8. \n\t\tA monochrome screen is stored as a single array of bytes, allowing eight consecutive pixels to be stored in one byte.
    \n\t\tThe screen has width w, where w is divisible by 8 (that is, not byte will be split across rows).
    \n\t\tThe height of the screen, of course, can be derived from the length of the array and the width.
    \n\t\tImplement a function drawHorizontalLine(byte[] screen, int width, int x1, int x2, int y) which draws a horizontal line from (x1, y) to (x2, y).\n\t<\/li>\n<\/ol>\n","protected":false},"excerpt":{"rendered":"

    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 … Continue reading →<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_exactmetrics_skip_tracking":false,"_exactmetrics_sitenote_active":false,"_exactmetrics_sitenote_note":"","_exactmetrics_sitenote_category":0,"footnotes":""},"categories":[6],"tags":[],"class_list":["post-490","post","type-post","status-publish","format-standard","hentry","category-cracking-the-coding-interview"],"_links":{"self":[{"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=\/wp\/v2\/posts\/490","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=490"}],"version-history":[{"count":3,"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=\/wp\/v2\/posts\/490\/revisions"}],"predecessor-version":[{"id":604,"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=\/wp\/v2\/posts\/490\/revisions\/604"}],"wp:attachment":[{"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=490"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=490"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=490"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}