Bit Manipulation

◾ 어떤 숫자와 1을 &연산하면 홀수, 짝수 여부를 확인할 수 있다.

 

i번째 비트 추출

int getIthBit(int n, int i) {
    int mask = 1<<i;
    return n & mask;
}

 

 

i번째 비트 변경

◾ 1로 변경

void setIthBit(int& n, int i) {
    int mask = (1<<i);
    n = (n | mask);
}

 

◾ 0으로 변경

void clearIthBit(int& n, int i) {
    int mask = ~(1<<i);
    n = (n & mask);
}

 

◾ 0 또는 1로 변경

void updateIthBit(int& n, int i, int v) {
    clearIthBit(n, i);
    int mask = (v<<i);
    n = (n | mask);
}

 

 

i번째까지의 비트 변경

◾ 끝에서 i번째까지 0으로 변경

void clearLastBits(int& n, int i) {
    int mask = (-1 << i);
    n = (n & mask);
}

 

◾ i에서 j번째까지 0으로 변경

void clearBitInRange(int& n, int i, int j) {
    int a = (-1<<j+1);
    int b = (1<<i)-1;
    int mask = a | b;
    n = n | mask;
}

 

◾ i에서 j번째까지 임의의 비트로 변경 (replace)

void replaceBits(int& n, int m, int i, int j) {
    clearBitInRange(n, i, j);
    int mask = (m << i);
    n = (n | mask);    
}

 

 

2의 거듭 제곱수 확인

bool isPowerOfTwo(int n) {
    return !(n & (n-1));
}
/*
 1000 -> 8	 1001 -> 9
&0111 -> 7	&1000 -> 8
-----		 ----
 0000 -> 0	 1000 -> 8 (!=0)

어떤 숫자가 2의 거듭 제곱수라면 n & (n-1) == 0이 성립한다.

 

 

비트 개수 찾기

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

시간 복잡도는 O(logN)이다.

 

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

1의 개수만큼 루프를 돌기때문에 조금 더 빠르다.

 

 

빠른 거듭제곱 계산

int fastExponentiation(int a, int n) {
    int ans = 1;
    
    while (n > 0) {
        int last_bit = n & 1;
        if (last_bit) ans *= a;
        a *= a;
        n = n >> 1;
    }
    
    return ans;
}

a^5 = a^(1+4)를 이용한다. 거듭제곱에 의한 오버플로우를 유의해야 한다.

비트 연산이 아닌 거듭제곱을 하게되면 시간복잡도는 O(n)이지만 비트 연산은 O(log n)이다.

 

 

10진수를 2진수로 변환하기

int convertToBinary(int n) {
    int ans = 0;
    int p = 1;
    
    while (n > 0) {
        int last_bit = n & 1;
        ans += last_bit * p;
        
        p *= 10;
        n = n >> 1;
    }
    
    return ans;
}

 

 

그 외 활용

◾ 배열 내의 유일한 값 찾기

어떤 배열에 단 하나의 값만 1개, 그외 다른 값은 2개씩 존재한다고 했을때 선형으로 접근하여 모든 수에 대해 xor 연산을 하면 유일한 값만 남게된다.

 

◾ 모듈러 연산

int power(int x, int y, int mod)
{
    int result = 1;
    while (y > 0) {
        int last_bit = y & 1;
        if (last_bit)
            result = (result * x) % mod;
        x = (x * x) % mod;
        y = y >> 1;
    }
    
    return result;
}

(a*b)%c = ((a%c)*(b%c))%c를 이용함과 동시에 빠른 거듭제곱 계산을 사용한다.