본문 바로가기
자료구조와 알고리즘/[서적] 해커의 기쁨 : 비트와 바이트 그리고 알고리즘

1. 기초 - 제일 오른쪽 비트 다루기

by 헛둘이 2022. 9. 10.
1-1. 한 워드의 제일 오른쪽 1비트를 끄는 법 (01011000 -> 01010000)
x & (x - 1)
#include <iostream>
#include <bitset>

using namespace std;

typedef char BYTE;

int main()
{
	BYTE b = 0b00001001; // 9
	bitset<8> showBit = b;
	
	cout << "before: " << showBit << endl;

	b = b & (b - 1);
    // b에서 -1 한다는 것은 00000001을 뺀다는 것으로
    // 맨 뒤에서 1을 빼려고 하는데 0이면 그 앞의 비트에서 빌려오고,
    // 그 앞의 비트가 0이면 다시 그 앞의 비트에서 빌려오고...반복
    // 그래서 맨 뒤의 비트가 꺼지게 된다.

	showBit = b;
	cout << "after: " << showBit << endl;
}
  • before : 00001001 = 9
  • after : 00001000 = 8 ( 맨 오른쪽 1비트가 사라졌다 )
  • 맨 오른쪽의 비트를 끄는 것이므로 00001010이어도 00001000이 된다.
  • 2의 거듭제곱이나 0임을 확인할 수 있는 방법으로도 쓰인다.
  • (2의 거듭제곱이면 비트 하나만 켜져 있을 것이고 그 하나를 끄면 0이 된다.)
  • 그런 비트가 없는 경우 결과 값은 0이다.

 

 

 

 

 

1-2 한 워드의 제일 오른쪽 0비트를 켜는 법 (10100111 -> 10101111)
x | (x + 1)
#include <iostream>
#include <bitset>

using namespace std;

typedef char BYTE;

int main()
{
	BYTE b = 0b00001001; // 9
	bitset<8> showBit = b;
	
	cout << "before: " << showBit << endl;

	b = b | (b + 1);
    // 00001001에 00000001을 더하면 맨 끝자리가 더해지며 0이 되고
    // 자리올림되며 0이 그 다음 0이 있는 자리를 찾아가게 된다.

	showBit = b;
	cout << "after: " << showBit << endl;
}
  • before : 00001001 = 9
  • after : 00001011 = 11 (맨 오른쪽 1비트가 켜졌다)
  • 그런 비트가 없는 경우 결과 값은 모든 비트가 1이다.

 

 

 

 

 

 

한 워드의 후행에 무리지은 1 비트들을 끄는 법 (11011111 -> 11000000)
x & (x + 1)
#include <iostream>
#include <bitset>

using namespace std;

typedef unsigned char BYTE;

int main()
{
	BYTE b = 0b11011111;
	bitset<8> showBit = b;
	
	cout << "before: " << showBit << endl;

	b = b & (b + 1);
	// 11011111 & 11100000 = 11000000
	// 맨 오른쪽부터 0으로 만들고 오면서 가장 먼저 만나는 0을 1로 만드는데
	// 그 1은 원래 비트에서 0이므로 & 연산을 통해 다시 0이 된다.

	showBit = b;
	cout << "after: " << showBit << endl;
}
  • before : 11011111
  • after : 11000000 (오른쪽의 1 덩어리들이 제거됨)
  • 그런 비트가 없는 경우 결과 값은 x이다.

 

 

 

 

 

한 워드의 후행에 무리지은 0 비트들을 켜는 법(10101000 -> 10101111)
x | (x - 1)
#include <iostream>
#include <bitset>

using namespace std;

typedef unsigned char BYTE;

int main()
{
	BYTE b = 0b10101000; // 168
	bitset<8> showBit = b;
	
	cout << "before: " << showBit << endl;

	b = b | (b - 1);
	// 후헹에서 시작해서 1을 만날 때까지 최상위 비트를 향해 1로 만들며 나아간다
	// 1을 만나면 그 1을 0으로 만들게 되고 그 과정에서 뒤의 비트들은 0이 된다.
	// 비트합(|) 연산을 통해 1로 변경된 비트들은 결과값에 그대로 반영된다. 

	showBit = b;
	cout << "after: " << showBit << endl;
}
  • before : 10101000
  • after : 10101111 ( 후행의 무리지은 0을 1로 세팅 )
  • 그런 비트가 없는 경우 결과 값은 x이다.

 

 

 

 

 

 

한 워드의 제일 오른쪽 0 비트만 1로 만드는 법 (10100111 -> 00001000)
~x & (x + 1)
#include <iostream>
#include <bitset>

using namespace std;

typedef unsigned char BYTE;

int main()
{
	BYTE b = 0b10100111; // 167
	bitset<8> showBit = b;
	
	cout << "before: " << showBit << endl;

	b = ~b & (b + 1);
	// 01011000 & 10101000 = 00001000
	// 기존 비트에서 반전된 끝에서 0번째 0이었던 비트가
	// 기존 비트에서 1 더해져서 맨 오른쪽 하나만 켜진 비트와 비트곱(&) 연산을 통해
	// 다른 값들은 반전 상태이므로 0으로 세팅되고 해당 비트만 결과값에 1로 반영된다.

	showBit = b;
	cout << "after: " << showBit << endl;
}
  • before : 10100111
  • after : 00001000 (기존 비트에서 맨 오른쪽 0이었던 비트만 1로 세팅되고 나머지 0으로 세팅)
  • 그런 비트가 없는 경우 결과 값은 0이다.

 

 

 

 

 

한 워드의 제일 오른쪽에 해당하는 1 비트만 0으로 만드는 법 (10101000 -> 11110111)
~x | (x - 1)
#include <iostream>
#include <bitset>

using namespace std;

typedef unsigned char BYTE;

int main()
{
	BYTE b = 0b10101000;
	bitset<8> showBit = b;
	
	cout << "before: " << showBit << endl;

	//cout << "-b : " << bitset<8>(~b) << endl;
	//cout << "(b - 1) : " << bitset<8>((b - 1)) << endl;

	b = ~b | (b - 1);
	// 01010111 | 10100111 = 11110111
	// 반전된 기존 비트열과 가장 우측에 있는 1을 0으로 만든 비트를 비트합(|)
	// 반전되었으니 가장 우측에 1이었던 비트가 0이 되고,
	// 기존 비트에서 1을 뺐으니 다시 가장 우측에 있는 비트가 0이 된 수를
	// 비트합 했으므로 그 자리만 0이 되고 나머지는 1로 세팅된다.

	showBit = b;
	cout << "after: " << showBit << endl;
}
  • before : 10101000
  • after : 11110111 (기존 비트에서 가장 우측에 있는 1을 0으로 세팅하고 나머지 1로 세팅)
  • 그런 비트가 없다면 결과는 모든 비트가 1임

 

 

 

 

 

 

한 워드의 후행에 무리지은 0 비트를 1로 세팅하고 나머지를 0으로 만드는 법 (01011000 -> 00000111)
~x & (x - 1)
#include <iostream>
#include <bitset>

using namespace std;

typedef unsigned char BYTE;

int main()
{
	BYTE b = 0b10101000;
	bitset<8> showBit = b;
	
	cout << "before: " << showBit << endl;



	b = ~b & (b - 1);
	// 01010111 & 10100111 = 00000111
	// 기존 수의 비트에서 반전된 비트와 기존 비트에서 1을 뺀 결과값을
	// 비트곱(&) 연산하면 뒤쪽 0이었던 무리의 비트들만 결과값에 1로 반영된다.

	showBit = b;
	cout << "after: " << showBit << endl;
}
  • before : 10101000
  • after : 00000111 (기존 비트에 후행에 무리지은 0만 1로 세팅되고 나머지는 0으로 세팅)
  • 그런 비트가 없다면 결과는 0

 

 

 

 

 

 

 

한 워드의 후행에 무리지은 1 비트들만 0으로 만들고 나머지는 1로 만드는 법 (10100111 -> 11111000)
~x | (x + 1)
#include <iostream>
#include <bitset>

using namespace std;

typedef unsigned char BYTE;

int main()
{
	BYTE b = 0b10100111;
	bitset<8> showBit = b;
	
	cout << "before: " << showBit << endl;


	b = ~b | (b + 1);
	// 01011000 | 10101000 = 11111000
	// 기존 숫자의 비트를 반전한 값과 기존 비트에 1을 더한 값을 비트합(|)

	showBit = b;
	cout << "after: " << showBit << endl;
}
  • before : 10100111
  • after : 11111000 (후열에 무리지은 1비트들을 0으로 세팅하고 나머지 1로 세팅)
  • 그런 비트가 없으면 모든 비트가 1인 경우임

 

 

 

 

 

제일 오른쪽 1비트만 남겨두는 법(01011000 -> 00001000)
x & (-x)
#include <iostream>
#include <bitset>

using namespace std;

typedef unsigned char BYTE;

int main()
{
	BYTE b = 0b10100111;
	bitset<8> showBit = b;
	
	cout << "before: " << showBit << endl;

	b = b & (-b);
	// 10100111 & 01011001 = 00000001
	// 반대 부호의 경우 기존의 비트를 반전하고 다시 1을 더하는 것이므로
	// 기존 비트와 비트곱(&)할 시 기존 비트에서 가장 마지막에 있는 1만 그대로 값을 가짐

	showBit = b;
	cout << "after: " << showBit << endl;
}
  • before : 10100111
  • after : 00000001 (가장 오른쪽에 있던 1만 그대로 남고 나머지는 0으로 세팅)
  • 그런 비트가 없는 경우 결과는 0

 

 

 

 

맨 오른쪽 1 비트와 그 오른쪽에 있는 0 비트를 1로 세팅하고 나머지 비트들을 0으로 만드는 법 (01011000 -> 00001111)
x ^ (x - 1)
#include <iostream>
#include <bitset>

using namespace std;

typedef unsigned char BYTE;

int main()
{
	BYTE b = 0b01011000;
	bitset<8> showBit = b;
	
	cout << "before: " << showBit << endl;

	b = b ^ (b - 1);
	// 01011000 ^ 01010111 = 00001111
	// 0에서 1을 빼기 위해서는 가장 우측에 있는 1까지 가는 길에 만나는 0을
	// 전부 1로 세팅하므로 기존 수와 그 부분에 대해서 반대되기 때문에
	// 배타적 논리합(^)에 의해 1로 세팅된다.
	

	showBit = b;
	cout << "after: " << showBit << endl;
}
  • before : 01011000
  • after : 00001111 ( 맨 우측에 있는 1비트와 그 오른쪽에 있는 0비트를 1로 세팅)
  • 맨 우측 1비트의 우측에 0이 없을 경우 결과값은 1이다.

 

 

 

 

 

 

 

제일 오른쪽에 있는 0비트와 그 후행 1비트를 전부 1로 세팅하는 법 (01010111 -> 00001111)
x ^ (x + 1)
#include <iostream>
#include <bitset>

using namespace std;

typedef unsigned char BYTE;

int main()
{
	BYTE b = 0b01010111;
	bitset<8> showBit = b;
	
	cout << "before: " << showBit << endl;

	b = b ^ (b + 1);
	// 01010111 ^ 01011000 = 00001111
	// 기존 비트와 기존 비트에 1을 더한 수를 배타적 논리합(^)을 함으로써
	// 서로 다른 비트만 1로 세팅되게 함
	// 1을 더하면 맨 우측 비트부터 시작해서 0을 만날 때까지 1을 0으로 만듦
	// 그러므로 1을 더했을 때 덧셈이 일어나는 구간들은 기존 수와 비교했을 때
	// 반대되는 경향을 띄므로 배타적 논리합(^)을 통해 1로 세팅된다

	showBit = b;
	cout << "after: " << showBit << endl;
}
  • before : 01010111
  • after : 00001111 ( 맨 후행 0과 그 우측의 1을 전부 1로 세팅하고 나머지는 0으로 세팅 )
  • 맨 우측 0비트의 우측에 1이 없는 경우 결과값은 1

'자료구조와 알고리즘 > [서적] 해커의 기쁨 : 비트와 바이트 그리고 알고리즘' 카테고리의 다른 글

2. 비트 연산으로 절댓값 함수 만들기  (0) 2022.09.11

관련글

댓글

티스토리툴바