Algorithms for programmers phần 6

Như đã đề cập ở trên, gcc phát ra chính xác hướng dẫn CPU có nghĩa là ở đây, ngay cả với nonconstant r. Cũng được thực hiện, gcc folks! Tất nhiên việc sử dụng rõ ràng của các hướng dẫn lắp ráp tương ứng không thể làm bất kỳ tác hại: | CHAPTER 7. SOME BIT WIZARDRY 107 return word rotated r bits to the left . toward the most significant bit return x r x BITS_PER_LONG-r As already mentioned gcc emits exactly the one CPU instruction that is meant here even with nonconstant r. Well done gcc folks Of course the explicit use of the corresponding assembler instruction cannot do any harm static inline ulong bit_rotate_right ulong x ulong r return word rotated r bits to the right . toward the least significant bit gcc optimizes the function to asm rorl 7cl __ if defined BITS_USE_ASM use x86 asm code return asm_ror x r return x r x BITS_PER_LONG-r endif where see FXT file auxbit static inline ulong asm_ror ulong x ulong r asm rorl cl r x 0 x c r return x Rotations using only a part of the word length are achieved by static inline ulong bit_rotate_left ulong x ulong r ulong ldn return ldn-bit word rotated r bits to the left . toward the most significant bit r must be ldn x x r x ldn-r if 0 ldn 7 BITS_PER_LONG x 1UL ldn -1 return x and static inline ulong bit_rotate_right ulong x ulong r ulong ldn return ldn-bit word rotated r bits to the right . toward the least significant bit r must be ldn .__ _ x x r x ldn-r if 0 ldn 7 BITS_PER_LOnG x 1UL ldn -1 return x Some related functions like static inline ulong cyclic_match ulong x ulong y return r if x rotate_right y r else return 0UL in other words returns how often the right arg must be rotated right to match the left or equivalently how often the left arg must be rotated left to match the right ulong r 0 do if x y return r y bit_rotate_right y 1 CHAPTER 7. SOME BIT WIZARDRY 108 while r BITS_PER_LONG return 0UL or static inline ulong cyclic_min ulong x return minimum of all rotations of x ulong r 1 ulong m x do x bit_rotate_right x 1 if x m m x while r BITS_PER_LONG return m can be found in FXT file auxbit Bitwise zip The bitwise zip operation when straight forward .