Chapter 5 from Elements of Programming Interviews

Parity
public class Parity2 {
  public static short parity2(long x) {
    short result = 0;
    while (x != 0) {
      result ^= 1;
      x &= (x - 1); // drops the lowest set bit of x.
    }
    return result;
  }
}
public class Parity3 {
  private static short[] precomputedParity;
  static {
    precomputedParity = new short[1 << 16];
    for (int i = 0; i < (1 << 16); ++i) {
      precomputedParity[i] = Parity1.parity1(i);
    }
  }
  public static short parity3(long x) {
    return (short) (precomputedParity[(int) ((x >> 48) & 0xFFFF)]
        ^ precomputedParity[(int) ((x >> 32) & 0xFFFF)]
        ^ precomputedParity[(int) ((x >> 16) & 0xFFFF)] 
        ^ precomputedParity[(int) (x & 0xFFFF)]);
  }
}

Swap bits
  public static long swapBits(long x, int i, int j) {
    if (((x >> i) & 1) != ((x >> j) & 1)) {
      x ^= (1L << i) | (1L << j);
    }
    return x;
  }

Reverse bits
  private static ArrayList<Long> precomputedReverse = new ArrayList<Long>();
  private static long reverseBits(long x, int n) {
    for (int i = 0, j = n; i < j; ++i, --j) {
      x = SwapBits.swapBits(x, i, j);
    }
    return x;
  }
  private static void createPrecomputedTable() {
    for (int i = 0; i < (1 << 16); ++i) {
      precomputedReverse.add(reverseBits(i, 15));
    }
  }
  public static long reverseBits(long x) {
    return precomputedReverse.get((int) ((x >> 48) & 0xFFFF))
        | precomputedReverse.get((int) ((x >> 32) & 0xFFFF)) << 16
        | precomputedReverse.get((int) ((x >> 16) & 0xFFFF)) << 32
        | precomputedReverse.get((int) (x & 0xFFFF)) << 48;
  }
  
closestIntegerSameBits
  public static long closestIntegerSameBits(long x) {
    for (int i = 0; i < 63; ++i) {
      if ((((x >> i) & 1) ^ ((x >> (i + 1)) & 1)) != 0) {
        x ^= (1L << i) | (1L << (i + 1)); // swaps bit-i and bit-(i + 1)
        return x;
      }
    }

    // Throw error if all bits of x are 0 or 1
    throw new RuntimeException("all bits are 0 or 1");
  }

  public static int setBit(int x, int bit, boolean setValue) {
    return setValue ? x | (1 << bit) : x & ~(1 << bit);
  }
Power set or Combination
public static void generatePowerSet(ArrayList<Integer> S) {
for (int i = 0; i < (1 << S.size()); ++i) {
int x = i;
while (x != 0) {
int tar = (int) (Math.log(x & ~(x - 1)) / LOG_2);
System.out.print(S.get(tar));
if ((x &= x - 1) != 0) {
System.out.print(",");
}
}
System.out.println();
}
}
  
  private static void generatePowerSetHelper(ArrayList<Integer> S, int idx,
      LinkedList<Integer> res) {
    if (!res.isEmpty()) {
      // Print the subset.
      Iterator<Integer> iterator = res.iterator();
      while (iterator.hasNext()) {
        System.out.print(iterator.next());
        if (iterator.hasNext()) {
          System.out.print(",");
        }
      }
    }
    System.out.println();

    for (int i = idx; i < S.size(); ++i) {
      res.offerLast(S.get(i));
      generatePowerSetHelper(S, i + 1, res);
      res.pollLast();
    }
  }  

Base Convert
public static String convertBase(String s, int b1, int b2) {
boolean neg = s.startsWith("-");
int x = 0;
for (int i = (neg ? 1 : 0); i < s.length(); ++i) {
x *= b1;
x += Character.isDigit(s.charAt(i)) ? s.charAt(i) - '0' : s
.charAt(i) - 'A' + 10;
}

StringBuilder ans = new StringBuilder();
while (x != 0) {
int r = x % b2;
ans.append((char) (r >= 10 ? 'A' + r - 10 : '0' + r));
x /= b2;
}

if (ans.length() == 0) {
ans.append('0');
}
if (neg) {
ans.append('-');
}
ans.reverse();
return ans.toString();
}

GCD without multiplication, division or modulus operations
public static long elementaryGCD(long x, long y) {
if (x == 0) {
return y;
} else if (y == 0) {
return x;
} else if ((x & 1) == 0 && (y & 1) == 0) { // x and y are even.
return elementaryGCD(x >> 1, y >> 1) << 1;
} else if ((x & 1) == 0 && (y & 1) != 0) { // x is even, y is odd.
return elementaryGCD(x >> 1, y);
} else if ((x & 1) != 0 && (y & 1) == 0) { // x is odd, y is even.
return elementaryGCD(x, y >> 1);
} else if (x > y) { // both x and y are odd, and x > y.
return elementaryGCD(x - y, y);
}
return elementaryGCD(x, y - x); // both x and y are odd, and x <= y.
}


PrimeSieve
public static ArrayList<Integer> generatePrimesFrom1toN(int n) {
int size = (int) Math.floor(0.5 * (n - 3)) + 1;
// isPrime[i] represents (2i + 3) is prime or not.
ArrayList<Integer> primes = new ArrayList<Integer>(); // stores the
// primes
// from 1 to n.
primes.add(2);
boolean[] isPrime = new boolean[size];
Arrays.fill(isPrime, true);
for (long i = 0; i < size; ++i) {
if (isPrime[(int) i]) {
int p = (int) ((i << 1) + 3);
primes.add(p);
// Sieving from p^2, whose index is 2i^2 + 6i + 3.
for (long j = ((i * i) << 1) + 6 * i + 3; j < size; j += p) {
isPrime[(int) j] = false;
}
}
}
return primes;
}
Given two axis-aligned rectangles A and B. Write a function to determine if the two rectangles overlap.
http://leetcode.com/2011/05/determine-if-two-rectangles-overlap.html

! ( P2.y < P3.y || P1.y > P4.y || P2.x < P3.x || P1.x > P4.x )
( P2.y ≤ P3.y && P1.y ≥ P4.y && P2.x ≥ P3.x && P1.x ≤ P4.x )

  public static boolean isIntersect(Rectangle R, Rectangle S) {
    return R.x <= S.x + S.width && R.x + R.width >= S.x
        && R.y <= S.y + S.height && R.y + R.height >= S.y;
  }

  public static Rectangle intersectRectangle(Rectangle R, Rectangle S) {
    if (isIntersect(R, S)) {
      return new Rectangle(Math.max(R.x, S.x), Math.max(R.y, S.y), Math.min(R.x
          + R.width, S.x + S.width)
          - Math.max(R.x, S.x), Math.min(R.y + R.height, S.y + S.height)
          - Math.max(R.y, S.y));
    } else {
      return new Rectangle(0, 0, -1, -1); // no intersection.
    }
  }
Multiply no add operation
public static long addNoOperator(long a, long b) {
long sum = 0, carryin = 0, k = 1, tempA = a, tempB = b;
while (tempA != 0 || tempB != 0) {
long ak = a & k, bk = b & k;
long carryout = (ak & bk) | (ak & carryin) | (bk & carryin);
sum |= (ak ^ bk ^ carryin);
carryin = carryout << 1;
k <<= 1;
tempA >>= 1;
tempB >>= 1;
}
return sum + carryin;
}

public static long multiplyNoOperator(long x, long y) {
long sum = 0;
while (x != 0) {
// Examine the lg(k)-th bit of x.
if (x % 2 != 0) {
sum = addNoOperator(sum, y);
}
x >>= 1;
y <<= 1;
}
return sum;
}

Divide No Operation
  public static long divideXbyYBinSearch(long x, long y) {
    if (x < y) {
      return 0;
    }

    int powerLeft = 0;
    int powerRight = 8 << 3;
    int powerMid = -1;
    while (powerLeft < powerRight) {
      int tmp = powerMid;
      powerMid = powerLeft + ((powerRight - powerLeft) >> 1);
      if (tmp == powerMid) {
        break;
      }
      long yshift = y << powerMid;
      if ((yshift >> powerMid) != y) {
        // yshift overflowed, use a smaller shift.
        powerRight = powerMid;
        continue;
      }
      if ((y << powerMid) > x) {
        powerRight = powerMid;
      } else if ((y << powerMid) < x) {
        powerLeft = powerMid;
      } else {
        return (1L << powerMid);
      }
    }
    long part = 1L << powerLeft;
    return part | divideXbyYBinSearch(x - (y << powerLeft), y);
  }

  // @include
  public static long divideXbyY(long x, long y) {
    long res = 0;
    while (x >= y) {
      int power = 1;
      // Checks (y << power) >= (y << (power - 1)) to prevent potential
      // overflow of unsigned.
      while ((y << power) >= (y << (power - 1)) && (y << power) <= x) {
        ++power;
      }

      res += 1L << (power - 1);
      x -= y << (power - 1);
    }
    return res;
  }