[Coding Interview] 비트 관련 문제

 

10진법과 2진법 테이블(32bit signed short기준)   0 : 00000000 00000000 1 : 00000000 00000001 2 : 00000000 00000010 3 : 00000000 00000011 4 : 00000000 00000100 ..... 32761 : 01111111 11111001 32762 : 01111111 11111010 32763 : 01111111 11111011 32764 : 01111111 11111100 32765 : 01111111 11111101 32766 : 01111111 11111110 32767 : 01111111 11111111 (max) -32768 : 10000000 00000000 (min) -32767 : 10000000 00000001 -32766 : 10000000 00000010  -32765 : 10000000 00000011  -32764 : 10000000 00000100  -32763 : 10000000 00000101  ..... -5 : 11111111 11111011 -4 : 11111111 11111100  -3 : 11111111 11111101  -2 : 11111111 11111110  -1 : 11111111 11111111 0 : 00000000 00000000  1 : 00000000 00000001  ......

 

 

 

문제 : int 값 n이 주어졌을 때, n의 비트를 출력하라.   아래 코드와 같은 방식으로, 오른쪽으로 한 칸씩 옮겨가며 1과 & 연산한 값을 stack 에 저장해두고 출력하면 된다.

	public String printBit(int num){
		StringBuilder sb = new StringBuilder();
		for(int i=0; i<32; i++){
			sb.append(num&1);
			num>>>=1;
		}
		return sb.reverse().toString();
	}

혹은 아래 사이트에 정리가 잘 되어 있으니 이 사이트의 내용을 참고한다. 참고

 

 

 

문제 : 정수 N 의 비트 값에서 1의 개수를 구하라.   정수 N 을 오른쪽 shift 해가면서 1과 and(&) 연산했을 때 1이면 count를 올리는 식으로 구현이 가능하다.   for(int i=n; i!=0; i>>>=1){     if( (i & 1) == 1) count++; }   재밌게도 위의 방법 외에 아래처럼 n & (n-1) 을 계속 해가며 0으로 만드는 횟수를 셀 수도 있다. 직관적으로 이게 왜 되는지 이해는 안 되지만 -_-;   for(int i=n; i!=0; i= i & (i-1) ){     count++; }

 

문제 : 숫자 n 이 주어진다. 모든 bit 가 1인 변수를 만들고, 아래에서 n개 만큼만 0으로 만들어라.   예를 들어 n 이 3일 때 1111 1000   n이 5일 때 1110 0000   모든 bit 가 1인 변수는 -1이다. (-1 의 bit 는 1111 1111) 혹은 ~0 을 대신 사용해도 좋다.   여기서 n 만큼 왼쪽 shift 연산을 사용하면 << 된다.

 

 

문제 : 숫자 n 이 주어진다. 모든 bit 가 0인 변수를 만들고, 아래에서 n개 만큼만 1로 만들어라.   예를 들어 n 이 3일 때 0000 0111   n이 5일 때 0001 1111   아래 코드처럼 1을 n번씩 옮겨가며 더해줘도 된다.   int n = 6; int bit = 0; int mask=1; while(n-->0){   bit+=mask;   mask<<=1; }   혹은 아래 코드로, n개의 1을 갖는 값을 한번에 만들어서 더해줘도 된다.   int n = 6; int bit = 0; bit=bit + (( 1<<6 ) - 1);   (0100 0000을 만든 후 -1을 하면 0011 1111이 되기 때문에 한 번에 n개의 1을 만들 수 있다.)

 

 

 

문제 : ((n & (n-1))==0) 이 무엇을 하는 코드인지 설명하라.   바로 위에서 설명한 것처럼, 1<<6 같은 2의 배수값에서 -1을 하면 0의 bit 개수만큼 1이 채워지게 된다. 예를 들어 비트가 1000 인 값 8에서 -1을 하면 비트가 0111 인 7이 된다. 따라서 2의 배수값에서 -1한 값과 &을 하게되면 무조건 0이 나오게 된다. 위의 코드는 이 사실을 토대로, n이 2의 배수인지 아닌지를 확인하는 코드이다.   추가적으로 n이 0일때 -1을 하면 1111 1111 을 얻을 수 있고 & 하면 0이 된다. 따라서 위의 코드를 통해 n 이 0인지 아닌지 확인할 수 도 있다.

 

 

문제 : 정수 A를 정수 B로 변환하기 위해 바꿔야 하는 bit의 개수를 구하는 코드를 작성하라.   xor 를 이용하여 간단하게 풀 수 있다. 정수 A 에서 정수 B로 바꾸려면 bit가 다른 위치의 bit만 0->1 , 1->0 으로 바꿔주면 되는데 AxorB(A^B) 를 이용하면 그 다른 위치에만 1 값이 들어가게 된다.   아래 코드를 보자.

		short a = 20061;
		short b = -9179;
		printBit(a); //01001110 01011101
		printBit(b); //11011100 00100101
		short c = (short) (a^b);
		printBit(c); //10010010 01111000
		
		int sum=0;
		for(int i=0; i<16; i++){
			if((c&1)==1) sum++;
			c>>>=1;
		}
		System.out.println(sum); //7
        
//아래는 개선된 코드

for(short c = (short)(a^b); c!=0; c>>=1){
    sum++;
}