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;
}
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;
}