位操作(Hacker's Delight)

    技术2025-07-11  8

       1、将一个word的最右侧为1的位改为0,也可以用来检查一个无符号整数是否为2的幂。(例如:0101 1000 ---> 0101 1000)

                                         x & (x-1)

                注:     x       0101 1000

                          x-1    0101 0111

                   x&(x-1)     0101 0000

          2、检查一个无符号整数是否为(2的n次方 – 1)

                                        x&(x+1)

          3、析出(isolate)最右侧为1的位。(或者可以这样说,在最右侧为1的位,把这个字分割)(例如:0101 1000 ----> 0000 1000)

                                          x&(-x)

               注:        x       0101 1000

                          -x       1010 1000

                        x&(-x)   0000 1000

         4、析出(isolate)最右侧为0的位。 (例如: 1010 0111 ----> 0000 1000)

                                        ~x&(x+1)

                注:    ~x     0101 1000

                        x+1     1010 1000

                   ~x&(x+1)0000 1000

          5、构造0后缀的掩码。(例如: 0101 1000 ------> 0000 0111)

                           ~x&(x-1)  或者 ~(x|(-x))  或者 (x&(-x)) –1

          6、构造最右侧为1的位以及0后缀的掩码 。(例如: 0101 1000 ------> 0000 1111)

                                         x^(x-1)

          7、传播最右侧为1的位。(例如: 0101 1000 ------> 0101 1111)

                                       x|(x-1)

          8、将最右侧连续的为1的位串,改成连续的为0的位串。(例如:0101 1000 ----> 0100 0000)

                                        ((x|(x-1)) +1)&x

             注:可以用来检查一个非负整数,是否存在(2的k次方-2的j次方)的形式(其中k>=j>=0)

    最新回复(0)