비트 연산

mohadang·2023년 4월 15일
0

System

목록 보기
7/12
post-thumbnail

bit 표현 갯수

일반적으로 int는 4 byte 타입이다(C/C++ 표준에 int가 4 byte 여야 한다는 규칙이 없다)
4 byte = 32 bit = 2 ^ 32

표현 가능한 수의 갯수는 2 ^ 32 갯수이다.(0 포함)

최대값은 어떻게 만들 수 있을까 ?
(2 ^ 32) - 1을 하면 모든 32 bit 모두를 1로 설정 가능하기에 최대값 표현 가능하다.

unsigned 데이터들은 이런 식으로 표현 가능 하지만 부호가 있는 데이터는 이런 식으로 구할 수 없다.

  • 업로드중..

맨 앞의 bit가 부호 비트이기에 값 표현에서 제외해야 한다
따라서 최대 양수는

2 ^ (32 - 1) - 1
01111111 ... 11111111

최소 음수는

2 ^ (32 - 1)
10000000 ... 00000000

기본 비트 연산

덧셈(+)

0110
0010
----
1000

뺄셈(-)

0110
0011
----
   2
0100
0011
----
0100
0011
----
   1
  2
0000
0011
----
   1
0000
0011
----
0011

곱셈(*)

 0101
 0011
 ----
 0101
0101
-----
01111

OR(|)

0011
0101
----
0111

AND(&)

0011
0101
----
0001

NOT(~)

0101
----
1010

XOR(^)

1101
0101
1000

Shift(<<)

1001
   2
----
0100

Shift(>>)

  1001
     2
  ----
  1110 or 0010

연산

덧셈, 뺄셈 모두 + 연산으로 가능하다.

덧셈

0101b = 5
0001b = 1
+
0110b = 6

뺄셈

0111b = 7
1111b = -1
+
0110b = 6

XOR(^)는 0과 연산하면 자기 자신이 나옴

XXXX
0000
----
XXXX

XOR(^)는 1과 연산하면 NOT(~)이 됨

 XXXX
 1111
 ----
~XXXX

자기 자신을 XOR(^)하면 0이 나옴

XXXX
XXXX
----
0000

AND(&)는 0과 연산하면 0이 나옴

XXXX
0000
----
0000

AND(&)는 1과 연산하면 자기 자신이 나옴

XXXX
1111
----
XXXX

자기 자신을 AND(&)하면 자기 자신이 나옴

XXXX
XXXX
----
XXXX

OR(|)는 0과 연산하면 자기 자신이 나옴

XXXX
0000
----
XXXX

이하 생략

bit 연산 응용

모든 bit를 1로 설정하고 싶을때

1000b - 0001b = 0111b

부호 있는 bit를 음수로 표현(2의 보수)

0100b = 4
1011b = 1의 보수(~ 반전)
1100b = 2의 보수(+ 1)

특정 비트 가져오기

9(1001)의 3번째 bit 가져오기

1000 = 1 << 3

1001
1000 &
-----
1000
BOOL get_bit(int num int i) {
  return (num & (1 << i)) != 0;
}

특정 비트 1 설정하기

9(1001)의 3번째 bit 1 설정하기

1000 = 1 << 3

1001
1000 |
-----
1000
int set_bit(int num, int i) {
  return num | (1 << i);
}

특정 비트 0 설정하기

9(1001)의 3번째 bit 0 설정하기

1000 = 1 << 3
0111 = ~1000

1001
0111 &
-----
0001
int cledar_bit(int num, int i) {
  return num & ~(1 << i);
}

특정 bit를 갱신

(XXXX XXXX)의 3번째 bit를 Y로 갱신

  1. 특정 bit를 0으로 만들기
0000 1000 = 1 << 3
1111 0111 = ~(0000 1000)

XXXX XXXX
1111 0111 &
---------
XXXX 0XXX
  1. 특정 bit를 Y로 설정하기
0000 Y000 = Y << 3

XXXX 0XXX
0000 Y000 |
---------
XXXX YXXX
int update_bit(int num, int i, int y) {
  return (num & ~(1 << i)) | (y << i);
}

인덱스번째 bit부터 왼쪽은 모두 0으로 설정

58(0011 1010)의 3번째 bit부터 왼쪽은 모두 0으로 설정

0000 1000 = 1 << 3
0000 0111 = (0000 1000) - 1

0011 1010
0000 0111 &
---------
0000 0010
int cledar_left_bit(int num, int i) {
  return num & ((1 << i) - 1);
}

인덱스번째 bit부터 오른쪽은 모두 0으로 설정

58(0011 1010)의 3번째 bit부터 오른쪽은 모두 0으로 설정

1111 1111 = -1
1111 0000 = (1111 1111) << (3 + 1)

0011 1010
1111 0000 &
---------
0011 0000
int cledar_right_bit(int num, int i) {
  return num & (-1 << (i + 1)) ;
}

오른쪽으로 1 shift는 2로 나누는 것이다

1010 = 10
0101 = 1010 >> 1 = 5
0010 = 1010 >> 2 = 2

진법 변환

참고 : https://velog.io/@mohadang/Joel-Coding-Problem-itoaradix

profile
mohadang

0개의 댓글