wiki:컴퓨터/비트연산

비트 연산

bit를 다루는 programming 관련 내용들을 정리하자. (2의 보수 기준)

  • 가장 오른쪽 1 비트 끄기 : x & (x-1) (01011000 -> 01010000)
  • 가장 오른쪽 1 비트 켜기 : x | (x+1) (10100111 -> 10101111)
  • 0중 가장 오른쪽에 있는 비트만 1로 : (~x & (x+1) (10100111 -> 00001000)
  • 1중 가장 오른쪽에 있는 비트만 0으로 : ~x | (x-1) (10101000 -> 11110111)
  • 뒤쪽 1 끄기 : x & (x+1) (10100111 -> 10100000)
  • 뒤쪽 0 켜기 : x | (x-1) (10101000 -> 10101111)
  • 뒤쪽 0들만 1로, 나머지는 0으로 : ~x & (x-1) 혹은 ~(x | -x) 혹은 (x & -x) - 1 (01011000 -> 00000111)
  • 뒤쪽 1들만 0으로, 나머지는 1로 : ~x|(x+1) (10100111 -> 11111000)
  • 가장 오른쪽 1비트만 구하기 : x & (-x) (01011000 -> 00001000)
  • 부호 없는 정수 x를 8의 배수 중 가장 가까운 숫자로 반내림 : x & -8 (55 -> 48)
  • 정수가 32비트 일 때, 1인 비트 수 세기

(Divide & conquer 방식으로, 32비트를 2비트씩 나눠서 1의 개수를 구하고, 그걸 4비트씩 나눠 1의 개수 구하고 다시 8비트, 그 다음은 16비트 순으로 구해서 더함)

x = (x & 0x55555555) + ( (x >> 1) & 0x55555555 );
x = (x & 0x33333333) + ( (x >> 2) & 0x33333333 );
x = (x & 0x0F0F0F0F) + ( (x >> 4) & 0x0F0F0F0F );
x = (x & 0x00FF00FF) + ( (x >> 8) & 0x00FF00FF );
x = (x & 0x0000FFFF) + ( (x >> 16) & 0x0000FFFF );
Last modified 3 years ago Last modified on Jun 20, 2016, 3:29:30 PM