연산자와 비트 연산

string print(int n) {
    stack<int> reverse;
    string ret = "";
    while (n != 0) {
        reverse.push('0' + n % 2);
        n /= 2;
    }
    while (reverse.size() != 0) {
        ret.push_back(reverse.top());
        reverse.pop();
    }
    return ret;
}
 
int toint(string s) {
    int ret = 0;
    int it = 1;
    for (int i = s.size() - 1; i >= 0; i--) {
        ret += (s[i] - '0')*it;
        it *= 2;
    }
    return ret;
}

1. 비트 연산자 정리

~ : 비트를 전부 뒤집는다.

& : 좌우 모든 자리의 비트를 각각 & 연산 한다

| : 좌우 모든 자리의 비트를 각각 | 연산 한다.

^ : 좌우 모든 자리의 비트를 각각 ^연산 한다.

>> : 비트를 1 우측 쉬프트한다

<< : 비트를 1 좌측 쉬프트한다

2. 기본 비트 연산

 - 0001000000 : 1 << i

** "1" 은 32비트 정수형이기 때문에 64비트가 필요하면 ll 아님 ull을 붙여야 한다.

- 1110111111 : ~(1<<i)

- 00001111111 : (1<<i)-1

- 11111000000 : ~((1<<i)-1)

- -x = ~x+1

** 더 쉽게 생각하는 법 : 비트를 뒤집으면(~x) 음수 - 1 이 된다!!

- x-1 오른쪽 첫 1을 0으로 바꾸고 그 아래 비트를 전부 1로 바꾼다.

  x+1 오른쪽 첫 0을 1로 바꾸고 그 아래 비트를 전부 0으로 바꾼다.

3. 응용 비트 연산

- 원소의 존재 여부

n&(1<<m)

- 비트의 추가, 제거, 토글

추가

n = n|(1<<m)

제거

n=n&(~(1<<m))

토글

n=n^(1<<m)

- 집합 연산

합집합

n = a|b

교집합

n = a&b

차집합

n = a&(~b)

- (1110011101000 >> 1000) 가장 오른쪽의 비트 구하기   

n = a&(-a)

- (1101101100 >> 1101101000) 최소 1 지우기

n = n&(n-1)

- (첫 1까지의 모든 0 1로 바꾸기

n = n|(n-1)

- 첫 0까지의 모든 1 0으로 바꾸기

n = n&(n+1)

- 최소 0 켜기

n = n|(n+1)

- 

9996. bitset<size> 자료구조

bitset<32> tmp(ba); // int ba를 tmp라는 bitset으로 생성한다

size 만큼의 bit를 가진 변수를 만든다. 각 비트를 접근할 수 있다.

양수와 음수 보수표현이 가능하다.

- 접근

tmp[13] 형식, bool이나 int나 char이나 암껄로 접근하면 된다.

- 연산

bitset간 bit연산 가능하다. 사칙연산은 안됨.. 정수나 다른 자료형과도 안됨

- 참고

최종 출력용으로 적합한듯. 근데 float형은 int로 캐스팅 한 후에 bitset에 저장되서 실제 값이 아니다.

9997. 진법 변환

헥스로..

cout << hex << 13232;

float를 binary로

- 비트 연산자는 int나 char 등의 정수 자료형에 해당(음수도 가능). floating point 연산에는 안된다.

floating point의 bit manipulation을 해야 하면 

union tester {

double f;

long long i;

};

을 사용하자. 더블의 바이트 값을 롱롱으로 읽어준다. 이 롱롱을 비트로 출력하면 된다.

정수를 binary로

bitset을 이용하자.

9998. 음수의 표현과 플로팅 포인트 표현

음수는 2의 보수법으로 표현된다.

2의 보수법은 MSB를 마이너스 값으로 표현해서 다 더한 값이다.

사칙연산과 비교 연산이 가능하다. 방법이 조금 다르다.

뺄셈은 2의 보수 표현을 더하는 식으로 구현한다.

floating point 표현법(IEEE754)

float(32bit) >> 1 부호 8 지수 23 숫자

double(64bit) >> 1 부호 11 지수 52 숫자

normalized 의 경우 ( exponent 1 ~ 마지막-1)

숫자 부분의 경우 1.xxxxx 의 xxxxx를 그대로 가져다 붙인 거고(2진법 분수이다)

부호는 부호고

지수 부분은 음수 지수까지 표현하기 위해 값 - 127 or 1023 을 해준 걸 곱한다(물론 2의 제곱)

참고로 8비트 float 지수부분의 경우 01111111 이 0을 뜻한다.

11 비트 double 지수부분의 경우에는 01111111111 이 0이다.

* 무한대 또는 계산안됨 등의 특수한 값을 표현하기 위해 지수부분 11111111 을 아껴둔다.

* 진짜 0을 표현하기 위해서, 그리고 매우 작은 값을 표현하기 위해 지수가 00000000 인 경우에는 값을 조금 다르게 표현하는데

값 = 부호 * 2^-126 * 0.xxxxxx(분수부분) 이렇게 1이 아니라 분수부분에 0을 쓴다.

값으로는 연속적인게 normalized 로 생각하면 2^-127*1.xxxxx 여야 하는데 분수 부분 하나를 지수 부분으로 보냈다고 생각하면 된다.

이게 좋은게 뭐냐면 0 표현이 가능해진다 ^^ 어짜피 2^-127 값을 표현하려면 E=00000000 이 되어야 하므로 값이 겹치는 경우도 없다.

9999. 기타 잡다한 사실

- 비트 연산자의 순위는 매우 낮은 편이므로 무조건 ( ) 괄호를 해 주어야 한다!!

- ! : 0이 아닌 int, float는 전부 1로, 0이나 0.00 은 1로 바꾸는 연산자

- float는 % 연산자가 작동 안한다!!

- 비교 연산자 ==, != 등은 int 와 float를 잘 비교해 준다. 아마 int를 float로 캐스팅 하는 거 같다. 다른 사칙연산자들과 같이

- 일반 연산자들은 인트와 플롯이 들어가면 플롯으로 캐스팅된다!!

- 16진수 상수 표현 : 0xaaba

- 2진수 상수 표현 : 0b1010101

10000. 코드 자료실

- LSB, MSB 쪽 비트 지우기

// clear all bits from msb to i
int clearMSB(int n, int i) {
    int m = (1 << i)-1;
    return n&m;
}
 
// clear all bits from i to LSB
int clearLSB(int n, int i) {
    int m = (1 << (i+1)) - 1;
    m = ~m;
    return n&m;
}