[자료구조] 시프트연산

시프트를 활용한 기본적인 연산인 N번째 비트를 핸들링하는 방법과 프로그래밍하는 방법에 대해서 알아보겠습니다.

 

 

1. GET - N 비트 가져오기

2. SET - N 비트 true

3. CLEAR - N 비트 false

4. CLEAR LEFT - N 비트 왼쪽으로 false

5. CLEAR RIGHT - N 비트 오른쪽으로 false

6. UPDATE - N 비트 true/false 제어하기

 

---

1. GET - N 비트 가져오기

boolean getBit( int num, int N ) {
	return num & ( 1 << N );
}

• num = 13; 0b1101;
• N = 3;
• 1을 왼쪽으로 N번 만큼 쉬프트하고 AND 연산을 통해 있다면 true 없다면 false를 반환하여 

3번째 비트를 확인하고 1이기 때문에 ture를 반환

 

2. SET - N 비트 ture

int setBit( int num, int N ) {
	return num | ( 1 << N );
}

• num = 5; 0b0101;
• N = 3;
• num | ( 1 << N ) = 13
• 1을 왼쪽으로 N번 만큼 쉬프트하고 OR 연산을 통해 N 비트를 1로 set 

num의 3번째 비트를 1로 변경

 

3. CLEAR - N 비트 false

int clearBit( int num, int N ) {
	return num & ~( 1 << N );
}

• num = 13; 0b1101;
• N = 3;
• num & ~( 1 << N ) = 5
• 1을 왼쪽으로 N번 만큼 쉬프트 -> NOT연산 -> OR 연산을 통해 N 비트를 0으로 set 

num의 3번째 비트를 0으로 변경

4. CLEAR LEFT - N 비트 왼쪽으로 false

int clearLeftBit( int num, int N ) {
	return num & ( 1 << N ) - 1;
}

• num = 173; 0b10101101;
• N = 3;
• num & ( 1 << N ) - 1 = 5
• 1을 왼쪽으로 N번 만큼 쉬프트 -> 1000 -1 = 0111 -> AND 연산을 통해 N 비트 왼쪽을 0으로 set 

num의 3번째에서 왼쪽을 0으로 변경

 

5. CLEAR RIGHT - N 비트 오른쪽으로 false

int clearRightBit( int num, int N ) {
	return num & -1 << ( N + 1 );
}

• num = 173; 0b10101101;
• N = 3;
• num & -1 << ( N + 1 ) = 160
• -1을 왼쪽으로 (N+1)번 만큼 쉬프트 -> AND 연산을 통해 N 비트 오른쪽을 0으로 set 

num의 3번째에서 오른쪽을 0으로 변경

 

6. UPDATE - N 비트 true/false 제어하기

int updateBit( int num, int N, boolean flag ) {
	return (num & ~(1 << N)) | << (flag ? 1 : 0) << N ;
}

• num = 181; 0b10110101;
• N = 3;
• flag = true;
• (num & ~(1 << N)) | (flag ? 1 : 0) << N  = 189
• 1을 왼쪽으로 N번 만큼 쉬프트 -> NOT 연산 -> AND 연산 -> flag에 의해 1을 N번을 쉬프트 -> OR 연산 -> N 번째 1으로 set

num의 3번 비트 1로 변경