u : unsigned

s : signed


>>  : 논리 시프트

>>u : 부호없는 산술 시프트

>>s : 부호있는 산술 시프트


ㄱ.기초

    a.비트 켜고 끄기


        1. 왼쪽의 한 비트를 켜고 끄기

            x | (x + 1) : 왼쪽의 한 비트를 켠다. 0100 -> 0101 -> 0111 -> 1111

            x & (x - 1) : 왼쪽의 한 비트를 끈다. 0111 -> 0110 -> 0100 -> 0000


        2. 좌측에서 처음 만나는 켜진비트만 끄기 or 꺼진비트만 켜기

            ~x | (x - 1) : 1010 0100 -> 1111 1011

            ~x & (x + 1) : 1010 0111 -> 0001 0000


        3. 좌측에서 처음 만나는 켜진비트만 켜기

            x & -x : 0110 0100 -> 0000 0100


        4. 좌측에서 처음 만나는 켜진비트와 그 후행비트켜기

            x ^ (x - 1) : 0110 0100 -> 0000 0111


        5. 선형 후행 켜진비트를 켜고 만나는 0도 같이 켜기

            x ^ (x + 1) : 0110 0111 -> 0110 1111


        6. 왼쪽의 선형 비트 켜고 끄기

            x | (x - 1) : 켜기. 0100 -> 0111

            x & (x + 1) : 끄기. 1011 -> 1000 -> 0000


        7. 좌 선형 후행비트만 켜고 끄기

            ~x & (x - 1)  or ~(x | -x)  or(x & -x) - 1

            0100 1000 -> 0000 0111

            ~x | (x + 1)

            1010 0111 -> 1111 1000


        8. 좌 선형 비트 끄기

            ~x | (x + 1) : 0110 1110 -> 0110 0000

                           0101 1100 -> 0100 0000



    b.절댓값 (32bit)

        y := x >>s 31 이라 둔다.


        1. abs

            (x ^ y) - y or(x + y) ^ y or  x - ((x << 1) & y)


            참고: mov eax, x

                 cdq

                 xor eax, edx

                 sub eax, edx


        2. nabs(-abs)

            y - (x ^ y)  or(y - x) ^ y or((x << 1) & y) - x



    c.두 수의 평균값 계산


        1. u일반적으로

            (x + y) >> 1


        2. u오버플로없이 계산

            Floor   : (x & y) + ((x ^ y) >>u 1)

            Ceiling : (x | y) - ((x ^ y) >>u 1)


        3. s오버플로없이 계산

            t := (x & y) + ((x ^ y) >>s 1) 라 하자

            Floor : t + ((t >>u 31) & (x ^ y))



    d.부호 함수(x<0 -> -1, x=0 -> 0, x>0 -> 1 )


        1. (x >>s 31) | (-x >>u 31)


        2. (-(x >>u 31)) | (-x >>u 3)



    e.다중 바이트 연산


        1. 덧셈

            ((x ^ y) & 0x80808080) ^ ((x & 0x7f7f7f7f) + (y & 0x7f7f7f7f))


        2. 뺄셈

            ((x ^ y) | 0x7f7f7f7f) ^ ((x | 0x80808080) - (y & 0x7f7f7f7f))



    f.레지스터 값 교환

        x := x ^ y

        y := y ^ x

        x := x ^ y

        

        x := x + y

        y := x - y

        x := x - y



    g.교대 설정


        1. 2개의 변수

            if (equal x a)

            x = b

            else x = a

            

            x := a + b - x or  x := a ^ b ^ x


        2. 3개의 변수

            if (equal x a)

            x = b

            else if (eqaul x b)

            x = c

            else

            a

            

            (( -(x = c)) & (a - c)) + (( -(x = a)) & (b - c)) + c

            or

            (( -(x = c)) & (a ^ c)) ^ (( -(x = a)) & (b ^ c)) ^ c



    h. 8의 배수 반올림/반내림


        1. 반올림

           (x + 7) & -8  or x + (-x & 7)

       

        2. 반내림

            x & -8

           (x >>u 3) << 3




아오 힘들어 다음 편은


    ㄴ.중간/활용 + 설명


        a.경계 점검


        b.비트 수 세기(pop count)


        c.워드 검색


        d.비트 바이트 뒤집기


언제 올라올지는 모릅니다.