2)Bitwise Operations:

Bitwise Operations:

  • Integers are represented as a string of bits (binary digits). Either big endian (akin to most significant place value at left) or little endian (akin to most significant place value at right). So three-hundred twenty-one as 321 or 123.
  • If unsigned integer, the number of bits used (the width) determines the numbers that can be encoded: 2^n.
    Unsigned means that the number is always positive; negatives aren't supported.
  • If signed integer, 4 methods; most common is 2's complement where negating a number (whether positive or negative) is done by inverting all the bits and then adding 1.
    • This has the advantage of having only one representation of 0 (instead of negative 0 and positive 0).
    • With 2's complement: "a signed integral type with n bits [...] represent[s] numbers from −2^(n−1) through 2^(n−1) − 1." So with 8 bits, the numbers from -128 to 127 can be encoded.
  • Java supports the following 2's complement signed numerical primitives (does not support unsigned numbers really):
    Also called integral data types.
    • byte -- 8 bits
      E.g.: from −128 to 127.
    • short -- 16 bits
      char -- unsigned 16 bits
    • int -- 32 bits
    • long -- 64 bits
  • Python supports 4 primary numeric types:
    https://docs.python.org/2/library/stdtypes.html
    • int -- Implemented using C's long, giving at least 32 bits of precision.
    • float -- Implemented using C's double, number of bits of precision depends on machine.
    • long -- Unlimited precision; expands to the limit of the available memory (not limited by number of bits).
    • complex -- Have a real and imaginary part, each of which is a float.
    • There are also fractions -- that hold rationals -- and decimal -- that hold floating-point numbers with user-definable precision.
  • Arithmetic:
    • Adding works as normal. Just remember that 1 + 1 = 10, so gotta carry the 1.
    • With subtraction, as normal but just be careful with borrowing from the left. If substracting 1 from 0 (0 - 1), borrow from the first place to the left where it's 1 - 0. If have to borrow multiple times, the leftmost digit (the one I'm really borrowing from) becomes a 0, the intervening digits get a decimal place added to them and then since they get borrowed from too a 1 is subtracted (so a 0 becomes 10 then 1 and a 1 becomes 11 then 10), and the original digit that needed to be increased becomes a 10.
      http://sandbox.mc.edu/~bennet/cs110/pm/sub.html
    • Multiplication can be done with left bitshifts. So because 3 * 5 is equivalent to 3 * (4 + 1), you can bitshift 3 to the left 2 places (which is 3 * 2^2 = 3 * 4) and then add 3 (3 * 1) back in.
    • Division can be done with right bitshifts, but just remember that it's integer division--rounded down basically.
  • Bitwise operations:
    • & = AND
    • ^ = XOR
    • | = (inclusive) OR
    • x << n = left-shifts x by n places (0s appended at the end). Equivalent to x * 2^n
    • x >> n = right-shifts x by n places using sign extension. Equivalent to x / 2^n (integer division).
      In Python, right-shift 0-fills.
    • x >>> n = right-shifts x by n places where 0s are shifted into the leftmost spots.
      Only in Java.
    • ~ = flips bits (unary operator)
  • Bit facts & tricks:
    Since operations are bitwise (occur bit by bit), these are all equivalent to their series-equivalents. E.g.: x ^ 0 is the same as x ^ 0s. If a statement is true for a single bit, it's true for a sequence of bits.
    • ^ (XOR)
      • x ^ 0 = x
      • x ^ 1 = ~x
        ~ = negation
      • x ^ x = 0
    • & (AND)
      • x & 0 = 0
      • x & 1 = x
      • x & x = x
    • | (inclusive OR)
      • x | 0 = x
      • x | 1 = 1
      • x | x = x
    • Swapping two values without a temporary variable:
      • a = a ^ b
      • b = a ^ b
      • a = a ^ b
      • E.g.: a = 2, b = 3; a = 0010, b = 0011.
        • a = a ^ b = 0010 ^ 0011 = 0001
        • b = a ^ b = 0001 ^ 0011 = 0010
        • a = a ^ b = 0001 ^ 0010 = 0011
        • a = 3, b = 2.
  • Common (and not-so-common) bit tasks:
    • Get the value of the bit at i in num. Specifically, return whether the ith bit is 1.
      • boolean getBit(int num, int i) {
        • return ((num & (1 << i)) != 0);
        • }
      • First left-shift 1 by i to get something like 00100000. Then AND with num to clear (set to 0) all the bits except the ith bit. If that value is not 0, then it's 1 and return true. Else it's 0 so return false.
      • To be more precise, the ANDing doesn't quite clear. It just makes it so that there are only two cases: all the bits are 0 or all the bits except the ith bit is 0. In the first case, the ith bit must be 0; in the second, it must be 1.
    • Set num's ith bit to 1.
      • int setBit(int num, int i) {
        • return num | (1 << i);
        • }
      • First left-shift 1 by i to again get something like 00100000. Then OR with num so that the ith bit will become 1 and the other values will not change. Recall that x OR-ing with 1 will always result in 1 and that x OR-ing with 0 will not change x.
    • Clear num's ith bit. Specifically, set the ith bit to 0.
      • int clearBit(int num, int i) {
        • int mask = ~(1 << i);
        • return num & mask;
        • }
      • Do something like the inverse of set (naturally). Left-shift 1 by i to again get something like 00100000. Then invert it so it looks like 11011111. AND with num: ANDing with 1 doesn't change anything, so the only bit that will change is the ith one, which will become a 0 if it isn't already.
    • Update num's ith bit with v. Specifically, set the ith bit to v.
      • int updateBit(int num, int i, int v) {
        • int mask = ~(1 << i);
        • return (num & mask) | (v << i);
        • }
      • The first part is equivalent to the clear bit method. Create a mask that looks like 11011111 then AND with num to clear the ith bit. Next, left-shift v by i bits so that v becomes a number where the ith bit is equal to what v was and all the other bits are 0. Finally, OR with the modified num (ith bit cleared) so that num's ith bit becomes 1 if v is 1 or is otherwise left as 0--recall that no other bits in num are modified since ORing with a 0 does not change the original.
    • Clear (unset) rightmost set bit. That is, change rightmost 1 to 0.
      • int clearRightmost(int num) {
        • return num & (num-1);
        • }
      • So, e.g., a 12 (1100) becomes a 1000 since ANDing 1100 and 1011 is 1000.
      • This forms the basis of the operation to determine parity.
    • Calculate parity. That is, return 1 (true) if the number of 1s is odd and 0 otherwise.
      EPI 5.1. http://www.geeksforgeeks.org/write-a-c-program-to-find-the-parity-of-an-unsigned-integer/ and https://graphics.stanford.edu/~seander/bithacks.html#OperationCounting
      • Naive method:
        • boolean getParity(int num) {
          • boolean parity = false;
          • while (num) {
            • parity = !parity;
            • num = num & (num - 1);
            • }
          • return parity;
          • }
        • Each time through the loop (until num is 0), clear the rightmost set bit and invert parity. Every odd number of clears, parity will be true / 1, so in the end, parity will be 1 if the number of 1s is odd and 0 otherwise.
        • Time complexity is the number of set bits.
        • We can also get the rightmost bit and xor with a 0/1 result. If 0, result doesn't change. Otherwise, result flips.
      • Not-so-naive method uses a precomputed lookup table. So for example the table could have the parities of the values from 0 through 15 inclusive. And then to find the parity of a 64 bit number, you would go 16 bits at a time by right shifting and XORing the 16 bit parities together.
        • This works because bitwise operations are associative (i.e., the grouping doesn't matter).
    • Get the Hamming distance.
      https://leetcode.com/problems/hamming-distance/#/description
      • "The Hamming distance between two integers is the number of positions at which the corresponding bits are different.
      • Given two integers x and y, calculate the Hamming distance."
      • def hammingDistance(self, x, y):
        • # Result has 1 only in places where corresponding bits are different.
        • z = x ^ y
        • ct = 0
        • # Count the number of 1s.
        • while z:
          • ct += 1
          • # Unsets the rightmost 1.
          • z &= z - 1
        • return ct
darkmode