[출처 : http://javawork.egloos.com/2297723]

비트를 다루는 문제는 인터뷰에서 자주 출제되는 문제입니다. 한국에서는 코드 가독성 및 유지보수 문제로 이런 코드는 잘 쓰지않는 것으로 아는데, 외국에서는 콘솔에서 게임 만들때 사용하던 방법이라 아직도 많이 사용하는 것 같습니다. 

가장 오른쪽의 1 -> 0
1011 -> 1010
1110 -> 1100
x = x & (x - 1);

가장 오른쪽의 0 -> 1
1100 -> 1101
1001 -> 1011
x = x | (x + 1);

가장 오른쪽 비트가 1인가
1101 -> true
1000 -> false
bool result = x & 1;

가장 오른쪽의 1을 끝까지 연장
100 -> 111
1000 -> 1111
1010 -> 1011
10100 -> 10111
x = x | (x - 1);

가장 오른쪽의 1을 끝까지 연장(좌측 비트들은 버림)
100 -> 111
1000 -> 1111
1010 -> 11
10100 -> 111
x = x ^ (x - 1);

1인 비트 세기 #1
1101 -> 3
unsigned int v = 13; // count the number of bits set in v
unsigned int c = 0; // c accumulates the total bits set in v
for (c = 0; v; v >>= 1)
{
    c += v & 1;
}

1인 비트 세기 #2
unsigned int v = 13; // count the number of bits set in v
unsigned int c = 0; // c accumulates the total bits set in v
for (c = 0; v; c++)
{
    v &= v - 1; // clear the least significant bit set
}

비트 뒤집기
11001010 -> 01010011
10101111 -> 11110101
unsigned char v = 202;     // input bits to be reversed
unsigned char r = v; // r will be reversed bits of v; first get LSB of v
int s = sizeof(v) * CHAR_BIT - 1; // extra shift needed at end
for (v >>= 1; v; v >>= 1)
{   
    r <<= 1;
    r |= v & 1;
    s--;
}
r <<= s; // shift when v's highest bits are zero

오른쪽의 연속적인 0비트 세기
1101000 -> 3
1000010 -> 1
unsigned char v = 104;  // input to count trailing zero bits
int c = 0;  // output: c will count v's trailing zero bits,
             // so if v is 1101000 (base 2), then c will be 3
if (v)
{
    v = (v ^ (v - 1)) >> 1;  // Set v's trailing 0s to 1s and zero rest
    for (c = 0; v; c++)
    {
      v >>= 1;
    }
}
else
{
    c = CHAR_BIT * sizeof(v);
}

저작자표시
[출처 : http://ask.nate.com/qna/view.html?n=294920]

#include 〈stdio.h〉

#define toOne(a, n) (a | (1 << n))
#define toZero(a, n) ((a^0xffff)^((1 << n)^0xffff))

void main(void)
{
int a;
a = 0x01FF;
printf ("%4x＼n", a);
printf ("%4x＼n", toOne(a, 8));
printf ("%4x＼n", toZero(a, 8));
printf ("%4x＼n", toOne(a, 7));
printf ("%4x＼n", toZero(a, 7));
}


------------------------------------------------------------


32 bit 길이의 integer에서 특정 bit을
0이나 1로 바꿀 수 있는 기능을 말씀하시는 것 아닙니까? ^^
위에 만든 예제가 바로 그것인데요, 특정 bit을 0이나 1로
setting할 수 있도록 만든 것입니다.

1.
먼저, 특정 bit을 1로 만드는 경우는
원래의 수와 특정 bit만 1로 set이 되고 나머지 bit는 0인 수를
XOR하면 얻을 수 있습니다.

2.
특정 bit을 0으로 만드는 경우는
원래의 수를 bitwise XOR한 수와
특정 bit만 0으로 set되고 나머지 bit는 1인 수를
XOR하면 얻을 수 있습니다.

여기에서 toOne(a,n)이라 정의한 부분은
(물른 inline 함수 등으로 구현하면 더욱 좋겠지요)
어떤 수(a)에서 특정 번째 bit(n)만 1로 만드는 역할을 합니다.
이는 위에서 설명한 바와 같구요,
toZero(a,n)이라 정의한 부분은
특정 bit만 0으로 만드는 역할을 합니다.
이 때 (a^0xffff)라 한 부분은 주어진 수를
bitwise XOR하는 역할을 하고,
((1 << n)^0xffff)는 특정 bit만
0으로 set된 수를 반환합니다.

제가 만든 프로그램에서는 integer 0x1ff를 가지고
특정 bit을 0이나 1로 만드는 시험을 해 봤는데요... ^^
해 보시면 아시겠지만 아주 성공적이었습니다.
물론, 이 때 n >= 0이어야 겠죠.
n == 0인 경우에도 잘 동작합니다. ^^
저작자표시
[출처 : http://littletrue.egloos.com/3984092]

비트 연산자

비트 연산자는 비트 중심으로 연산할 때 사용하는 연산자입니다. 비트(bit)란 정보를 저장하는 가장 작은 단위로 그 값은 0이나 1입니다. 비트 조작은 가장 낮은 단계에서 시스템을 조작해야 할 경우에 필요하기 때문에 그런 부분까지 제어할 필요가 없다면 이 부분은 가볍게 읽거나 건너뛰어도 됩니다. 자바스크립트에서는 시스템 제어보다는 주로 암호나 인코딩을 위해 사용합니다.

여덟개의 비트가 연달아 있는 것을 바이트(byte)라고 합니다. 즉 1바이트는 8비트입니다. 8비트로 표현할 수 있는 수의 종류는 256(28)가지입니다. C나 C++, 파스칼처럼 문자 유형을 지원하는 프로그래밍 언어에서는 한 바이트가 한 글자를 나타냅니다. 
(여기에서의 한글자는 영문 한글자를 가리킵니다. 한글 한 글자를 표시하기 위해서는 2바이트가 필요합니다)

16진수는 각 자리가 4개의 이진 비트로 구성되기 때문에 이진 데이터를 표현할 때는 16진법이 가장 적당합니다. 아래 표는 0에서 F까지의 16진수 값과 그에 해당하는 2진수 값을 정리한 것입니다.

16진수

2진 표현

  

16진수

2진 표현

0

0000

  

8

1000

1

0001

9

1001

2

0010

A

1010

3

0011

B

1011

4

0100

C

1100

5

0101

D

1101

6

0110

E

1110

7

0111

F

1111

비트 연산자를 사용하면 데이터 비트별로 작업할 수 있습니다. 비트 연산자는 다음과 같습니다.

형식

이름

유형

&

비트 AND

binary

|

비트 OR

binary

^

비트 XOR (exclusive OR)

binary

~

비트 NOT

unary

<<

왼쪽 시프트(왼쪽 이동)

binary

>>

오른쪽 시프트

binary

>>>

Zero-fill right shift

binary

비트 AND

형식

 

피연산자1 & 피연산자2

비트 AND 연산자는 두 개의 비트를 비교하는 것인데, 두 개의 비트가 모두 1일 경우에만 결과값이 1이 됩니다. 

피연산자1

피연산자2

피연산자1 & 피연산자2

0

0

0

0

1

0

1

0

0

1

1

1

예를 들어 16진수 23과 72에 비트 AND 연산자를 사용하면 다음과 같습니다.

 

0

 

0

 

1

 

0

 

0

 

0

 

1

 

1

 

 

 

(0x23)

&

0

 

1

 

1

 

1

 

0

 

0

 

1

 

0

 

 

 

(0x72)

 

0

 

0

 

1

 

0

 

0

 

0

 

1

 

0

 

 

 

(0x22)
                                       

비트 AND 연산자는 어떤 숫자가 짝수인지 홀수인지 테스트할 때 많이 사용합니다. 2진수로 표현했을 때 홀수의 맨 마지막 비트는 1이고 짝수의 맨마지막 비트는 0입니다. 따라서 맨 마지막 비트의 값과 1을 비트 AND 연산했을 때 결과값이 1이면 홀수이고 0이면 짝수가 될 것입니다. 간단히 함수로 표현하면 다음과 같습니다.

function checkEven(myNumber) { // 짝수 체크 함수
    return (myNumber & 1 == 0) // 1과 비트 AND 연산했을 때 0이면 반환
}

비트 OR

형식

 

피연산자1 |피연산자2

OR 연산자는 배타적 OR 연산자라고도 하는데, 두 피연산자를 비교해서 최소한 하나만 1이면 결과값은 1이 됩니다.

피연산자1

피연산자2

피연산자1 | 피연산자2

0

0

0

0

1

1

1

0

1

1

1

1

다음은 연산  예입니다.

 

0

 

1

 

0

 

0

 

0

 

1

 

1

 

0

 

 

 

(0x46)

|

0

 

1

 

1

 

1

 

1

 

0

 

0

 

1

 

 

 

(0x79)

 

0

 

1

 

1

 

1

 

1

 

1

 

1

 

1

 

 

 

(0x7F)
                                       

비트 XOR

형식

 

피연산자1 ^ 피연산자2

비트 XOR는 (XOR를 읽을 때는 익스클루시브 OR로 읽음) 연산자는 피연산자 중 한 비트가 1이면 1을 반환하고 두 피연산자가 같으면(즉, 0과 0이거나 1과 1일때) 결과값이 0이 됩니다.

피연산자1

피연산자2

피연산자1 ^ 피연산자2

0

0

0

0

1

1

1

0

1

1

1

0

아래 연산은 비트 XOR 연산의 예입니다.

 

0

 

0

 

1

 

0

 

1

 

1

 

0

 

0

 

 

 

(0x2C)

^

1

 

0

 

1

 

0

 

0

 

0

 

1

 

1

 

 

 

(0xA3)

 

1

 

0

 

0

 

0

 

1

 

1

 

1

 

1

 

 

 

(0x8F)
                                       

비트 XOR 연산자는 XORing이라고 하는 간단한 암호 기법에서 사용합니다.

비트 NOT

비트 NOT 연산자는 피연산자 값의 반대값을 반환합니다. 그래서 이 연산자를 비트 플립 연산자(bit flip operator)라고도 부릅니다. 1은 0으로, 0은 1로 바꿉니다.

피연산자

~피연산자

0

1

1

0

예를 들어볼까요?

~ 00000000000000000000000001000110(2)  ☜ 70

    111111111111111111111111101110012  ☜ -71

주의 : 이 연산자는 모든 피연산자를 32비트로 사용합니다. 32비트가 아닌 정수를 사용한다면 자동으로 32비트로 만들어진 후 연산합니다.

시프트 연산자

시프트 연산자에는 두 가지 피연산자가 있습니다.

  • 이동시킬 값

  • 첫번째 피연산자를 이동시킬 비트 위치(숫자)

시프트 연산자는 피연산자를 32비트 정수로 바꾼 후 같은 유형의 결과값을 반환합니다. 시프트 연산자는 세 가지 종류가 있습니다.

  • 왼쪽 시프트 (<<)

  • 오른쪽 시프트 (>>)

  • Zero-fill right shift (>>>)

① Left shift

형식

 

피연산자1 << 피연산자2

왼쪽 시프트 연산자는 왼쪽에 있는 피연산자1을 피연산자2에서 지정한 비트수만큼 왼쪽으로 이동합니다. 모든 비트가 하나씩 왼쪽으로 이동하고 나면 오른쪽 맨 끝에 한자리가 비는데 이 자리는 0으로 채워집니다.

179(10) → 0xB3 → 10110011(2)

179 << 0    ☞

00000000000000000000000010110011

179 << 2    ☞

00000000000000000000001011001100

 

→ 010110011(2)

 

→ 0x2CC

 

→ 716(10)

이제 179를 왼쪽으로 2비트만큼 이동시키면 716이 된다는 것을 알게 되었습니다. 일반적으로 x << n(x를 왼쪽으로 n비트만큼 이동)를 계산하면 x * 2n와 같습니다. 위에서 살펴본 179 << 2의 경우에도 179 * 22 = 716입니다. 이 규칙은 음수의 경우에도 똑같이 적용됩니다.

오른쪽 시프트

형식

 

피연산자1 >>피연산자2

오른쪽 시피트 연산자는 피연산자의 부호를 그대로 유지합니다. 왼쪽 시프트 연산자와 마찬가지로 첫번째 피연산자를 두번째 피연산자크기만큼 오른쪽으로 이동시킵니다. 오른쪽으로 이동하면서 넘어간 숫자들은 무시됩니다. 정수의 부호는 첫번째 부호에 저장되는데 부호를 그대로 유지하려면 첫번째 비트는 그냥 두어야겠죠? 그리고 나머지 31개의 비트만 오른쪽으로 이동시키면 됩니다. 오른쪽으로 이동시킨 후 왼쪽에 새로 생기는 비트들은 부호 비트에 따라 0이나 1이 저장됩니다. 부호 비트가 0이면 새로운 비트들을 모두 0으로 채우고, 부호 비트가 1이면 새로운 비트를 1로 채웁니다.

176(10) → 0xB0 → 10110000(2)

176 >> 0    ☞

00000000000000000000000010110000

170 >> 3    ☞

0    0000000000000000000000010110000

 

→ 00000000000000000000000000010110

 

→ 10110(2) → 0x16

 

→ 22(10)

음수일 경우에는 어떻게 될까요?

-17(10) → 11111111111111111111111111101111 (2)    (참고1)

-17 >> 0    ☞

11111111111111111111111111101111

-17 >> 3    ☞

   11111111111111111111111111101111

 

→ 11111111111111111111111111111101

 

→ -3(10)  (참고2)

※ 참고1 : -17을 이진수로 표현하려면 일단 17을 2진수로 표현한 후(10001) 각 비트마다 2의 보수 값을 구하고 그 결과에 1을 더하면 됩니다.

① 17에 대한 2진수 구함 : 10001
② 2의 보수로 바꿈 : 01110
③ 1을 더함 : 01110+1 → 01111
④ 따라서 -17은 11...101111

※ 참고2 : 11....1101을 10진수로 표현하려면...

① 맨 앞 비트가 1이므로 음수임을 알 수 있다
② 10진수로 바꾸기 위해 2의 보수로 변환 : 000..0010
③ 1을 더함 : 0010 + 1 → 0011 → 3
④ 원래 음수였으므로 -3

오른쪽 이동 후 0으로 채우기

형식

 

피연산자1 >>> 피연산자2

이 연산자는 오른쪽 시피트 연산자와 똑같이 동작하는데 단, 오른쪽으로 이동한 후 새로 생기는 왼쪽의 빈 비트를 0으로 채운다는 점만 다르답니다. 따라서 양수일 경우 오른쪽 시프트했을 경우와 결과값이 같지만 음수일 경우 전혀 다른 값이 나오게 됩니다.

 

저작자표시

+ Recent posts

티스토리툴바