비트연산

Bit Twiddling Hacks 에서 정리되어 있는 비트 관련 내용 몇 가지 감명 받거나 유용해보이는 것 위주로 정리

바이트 관련

워드에 0인 바이트가 있는지 확인하기

워드는 프로세서가 기본적으로 처리할수 있는 단위를 말하며 이 문서에선 4bytes를 의미한다. 4bytes 내에 0바이트가 존재하는지 확인하는 것으로서 이를 활용하면 strlen 등을 최적화할 수 있다.

C
#define haszero(v) (((v)-0x01010101UL) & ~ (v) & 0x80808080UL)

이 매크로를 사용하면 0인 바이트가 있을때 해당바이트 최상위 비트가 1로 세팅된다.
리틀엔디언 세번째바이트가 0일 경우 0x800000 첫번째 바이트가 0일 경우 0x80 이런 식으로 결과가 나오게 된다.

그럼 glibc/strlen.c 의 소스코드를 보자

C
  /* Instead of the traditional loop which tests each character,
     we will test a longword at a time.  The tricky part is testing
     if *any of the four* bytes in the longword in question are zero.  */
  for (;;)
    {
      longword = *longword_ptr++;

      if (((longword - lomagic) & ~longword & himagic) != 0)
	{
	  /* Which of the bytes was the zero?  If none of them were, it was
	     a misfire; continue the search.  */

	  const char *cp = (const char *) (longword_ptr - 1);

	  if (cp[0] == 0)
	    return cp - str;
	  if (cp[1] == 0)
	    return cp - str + 1;
	  if (cp[2] == 0)
	    return cp - str + 2;
	  if (cp[3] == 0)
	    return cp - str + 3;

if 문 안의 조건문을 보면 lomagic 이랑 himagic 위 매크로의 패턴과 같다. 워드 단위 즉 4바이트 씩 포인터를 증가시키면서 단지 4 Operation 만으로 4바이트씩 건너뛰며 0이 있는지 검사하여 매우 빨라진다. Loop은 포인터를 증가시킨뒤 4 Operation을 수행하고 0이 아닌지 비교하기 때문에 분기예측 적중률도 매우 높을 것이다.

워드에 N보다 작은 바이트가 있는지 확인하기

사실 위의 0인 바이트를 찾아내는 것은 지금 얘기하고자 하는 것의 부분집합이라고 할 수 있다.

C
#define hasless(x, n) (((x)-~ 0UL / 255 * (n)) & ~ (x) & ~ 0UL / 255 * 128)

특정 N값 보다 작은 바이트가 존재하는지 찾는 매크로는 위와 같다. 이때 각 부분을 미리 풀어보면 ‘0과 같은 바이트를 찾기’ 와 매우 유사하다.

C
~ 0UL / 255 * (0x01) // 0x01010101 
~ 0UL / 255 * 128    // 0x80808080
hasless(x, 0x01) (((x)-0x01010101) & ~ (x) & 0x80808080)

0x01 보다 작은 바이트를 찾는다고 하면 사실 0인 바이트를 찾는 것과 같은 것이다. 위를 응용하여 0x20 보다 작은 문자들을 찾는 예를 들수 있다. ascii code 에서 0x20 은 ‘space’ 문자이며 이보다 작은 문자들은 제어문자들로서 ‘\t’, ‘\n’, ‘\r’ 과 같은 문자들도 포함되어 있다. readline 등과 같은 빠른 구현을 할때 활용할 수 있다.