[Java] 자바의 이진 연산(비트 연산)

OR 연산과 AND 연산

OR 연산은 이진수의 각 자리수가 하나라도 1이면 해당 자릿수는 1, 아니면 0을 리턴

AND 연산은 이진수의 각 자리수 모두가 1이면 해당 자릿수는 1, 아니면 0을 리턴

 public static void main(String []args) {
    int n1 = 4; // 100
    int n2 = 5; // 101

    // OR 연산
    int n3 = n1 | n2;   // 101 -> 5
    // AND 연산
    int n4 = n1 & n2;   // 100 -> 4

    System.out.println(n3);
    System.out.println(n4);
 }

 

시프트 연산

이진수의 비트를 원하는 값만큼 이동시키는 연산

 public static void main(String []args) {
    int n1 = 4; // 100
    int n2 = 5; // 101

    // << 왼쪽 시프트
    int n3 = n1 << 2;   // 100을 왼쪽으로 두자리만큼 이동 -> 10000(16)

    // >> 오른쪽 시프트
    int n4 = n2 >> 1;   // 101을 오른쪽으로 한자리만큼 이동 -> 10(2)

    System.out.println(n3);
    System.out.println(n4);
 }

 

이진수 문자열을 int로 변환

public static void main(String []args) {
    int n = stringToInt("100"); // 4
    System.out.println(n);
    n = stringToInt("101"); // 5
    System.out.println(n);
 }

// 이진수 형식의 문자열을 int로 계산
static int stringToInt(String bitString) {
	int result = 0;
	for(int i=0; i<bitString.length(); i++) {
		if(bitString.charAt(i) == '1') {
        	// OR 연산과 시프트 연산
			result |= (1 << (bitString.length() - 1 - i));
		}
	}
	return result;
}

 

XOR 연산

이진수의 값의 각 자릿수가 서로 다를 경우, 1

 public static void main(String []args) {
    int n1 = 4; // 100
    int n2 = 5; // 101

    // XOR 연산
    int n3 = n1 ^ n2;   // 001(1)

    // 자릿수가 다른 경우, XOR 연산
    n1 = 8; // 10000
    int n4 = n1 ^ n2;   // 1000 ^ 101 = 1101(13)

    System.out.println(n3);
    System.out.println(n4);
 }

 

이진수 값의 각 자릿수 중의 1의 개수 구하기 / Brian Kernighan's Algorithm

 

Brian Kernighan's Algorithm의 원리는 다음과 같다

n-1의 값은 n이 가지고 있는 가장 오른쪽에 1부터 값이 변한다.

예시. n = 10100 -> n-1 = 10011

 

이후 두 값을 AND연산자 n & (n - 1) 해주면, 10000되며 가장 오른쪽에 있는 1이 제거된다.

이 연산을 반복하여 최종적으로 값이 0이 된다면, 반복한 연산의 개수는 n이 가지고있던 1의 개수와 같다.

public static void main(String []args) {
    int n1 = 4; // 100
    int n2 = 5; // 101
    int n3 = 7; // 111

    System.out.println(BKA(n1));    // 1
    System.out.println(BKA(n2));    // 2
    System.out.println(BKA(n3));    // 3
 }

 // Brian Kernighan's Algorithm
 static int BKA(int n) {
    int cnt = 0;

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