Data Structures
    Overview
    Number
    String
    Array
    Linked List
    Stack
    Hash
    Tree
    Trie
    Advanced Data Structure
    Probabilistic Data Structures
    Big O

Number

Updated: 2021-12-15

Bit Manipulation

To convert integers to Binary or Hex String:

System.out.println(Integer.toBinaryString(96));
System.out.println(Integer.toHexString(96));

To convert Binary or Hex string to integer:

Integer.parseInt("10010101010101010101010", 2);
Integer.parseInt("ffff", 16);

Basic operations:

// ffffffff
int max = ~0;

// 111111111111111
int ones = (1<<15) - 1;

// 11111111111111111000000000000000
int leftOnes = max - ones;

// 11111
int rightOnes = (1<<5) - 1;

// 11111111111111111000000000011111
int mask = leftOnes | rightOnes;

// 10010101000000000001010
int masked = Integer.parseInt("10010101010101010101010", 2) & mask;

Swap Two Integers

a = a ^ b;
b = a ^ b;
a = a ^ b;

Check If a Number is power of 2

n > 0 && ((n & (n-1)) == 0)

e.g.

  • k = 256
    • k = 1000000(binary)
    • k - 1 = 0111111
    • k & (k - 1) = 0

Count 1 in an Integer

int count(int n)
{
    int cnt = 0;
    while(n) {
        cnt += n & 1;
        n >>= 1;
    }
    return cnt;
}

or

int count(int n)
{
    int cnt = 0;
    while(n) {
        n &= (n-1);
        cnt++;
    }
    return cnt;
}

Count Trailing 0s in N!

int count(int n)
{
    int cnt = 0;
    while(n) {
        cnt += n / 5;
        n /= 5;
    }
    return cnt;
}

Find the Position of the Last 1 in Binary Result of N!

int count(int n)
{
    int cnt = 0;
    while(n) {
        n >>= 1;
        cnt += n;
    }
    return cnt;
}

Plus with Binary Operations

Add two integers without +, -, *, /

int bplus(int a, int b)
{
    if (b == 0)
        return a;
    int sum = a ^ b;
    int carry = a & b;
    bplus(sum, carry<<1);
}

Get Max without if-else

int getMax(int a, int b) {
    int c = a - b;
    int k = (c >> 31) & 0x1;
    int max = a - k * c;
    return max;
}