Notes from hackers delight

n_hd.txt

 Hacks

+--------------------------------+---------------+-------------------+-----------------------+
|Type                            |Formula        |Example            |Code Result            |
|                                |               |                   |                       |
+--------------------------------+---------------+-------------------+-----------------------+
|1.Test of number being power of |x & (x – 1)    |(e.g., 01011000 ⇒  |x = 8 result = 0, x = 9|
|2.                              |               |01010000)          |result = 8             |
|                                |               |                   |                       |
|                                |               |                   |                       |
|                                |               |                   |                       |
+--------------------------------+---------------+-------------------+-----------------------+
|2.  if number is power of 2,    |x | (x + 1)    |(e.g., 10100111 ⇒  |if num = 16 res = 31,  |
|then result is one less than the|               |10101111)          |if num = 10 res = 11   |
|next power of 2. Else the number|               |                   |                       |
|is incremented by 1             |               |                   |                       |
|                                |               |                   |                       |
|                                |               |                   |                       |
|                                |               |                   |                       |
|                                |               |                   |                       |
|                                |               |                   |                       |
|                                |               |                   |                       |
|                                |               |                   |                       |
|                                |               |                   |                       |
+--------------------------------+---------------+-------------------+-----------------------+
|3. if trailing 1's in the byte  |x & (x + 1)    |(e.g., 10100111 ⇒  |x = 8 result = 8, x = 9|
|return num or return num - 1. To|               |10100000)          |result = 8             |
|check if num = 2^n -1, 0, 1     |               |                   |                       |
|                                |               |                   |                       |
|                                |               |                   |                       |
|                                |               |                   |                       |
|                                |               |                   |                       |
|                                |               |                   |                       |
|                                |               |                   |                       |
|                                |               |                   |                       |
+--------------------------------+---------------+-------------------+-----------------------+
|4. to turn on the trailing 0’s  |x | (x– 1)     |(e.g., 10101000 ⇒  |x = 7 res = 7. x = 8   |
|in a word, producing x if none  |               |10101111)          |res = 15 , x = 9 res = |
|                                |               |                   |9                      |
|                                |               |                   |                       |
|                                |               |                   |                       |
|                                |               |                   |                       |
|                                |               |                   |                       |
+--------------------------------+---------------+-------------------+-----------------------+
|5. to create a word with a      |¬x & (x + 1)   |(e.g., 10100111 ⇒  |sample x = 7 , res = 0;|
|single 1-bit at the position of |               |00001000)          |                       |
|the rightmost 0-bit in x,       |               |                   |                       |
|producing 0 if none             |               |                   |                       |
|                                |               |                   |                       |
|                                |               |                   |                       |
|                                |               |                   |                       |
|                                |               |                   |                       |
|                                |               |                   |                       |
|                                |               |                   |                       |
|                                |               |                   |                       |
|                                |               |                   |                       |
+--------------------------------+---------------+-------------------+-----------------------+
|6. To create a word with a      |¬x | (x – 1)   |(e.g., 10101000 ⇒  |sample x = 16 res = 15,|
|single 0-bit at the position of |               |11110111)          |x = 7 res = 6          |
|the rightmost 1-bit in x,       |               |                   |                       |
|producing all 1’s if none       |               |                   |                       |
|                                |               |                   |                       |
|                                |               |                   |                       |
|                                |               |                   |                       |
|                                |               |                   |                       |
|                                |               |                   |                       |
|                                |               |                   |                       |
|                                |               |                   |                       |
|                                |               |                   |                       |
|                                |               |                   |                       |
+--------------------------------+---------------+-------------------+-----------------------+
|7. to isolate the rightmost     |x & (−x)       |(e.g., 01011000 ⇒  |x = 16 res = 16, x = 7 |
|1-bit, producing 0 if none      |               |00001000)          |res = 1, x = 6 res = 1 |
|                                |               |                   |                       |
|                                |               |                   |                       |
|                                |               |                   |                       |
|                                |               |                   |                       |
+--------------------------------+---------------+-------------------+-----------------------+
|8. to create a word with 1’s at |x ⊕ (x − 1)    |(e.g., 01011000 ⇒  |x = 15 res = 1, x = 16 |
|the positions of the rightmost  |               |00001111)          |d = 31, x = 17 d = 1   |
|1-bit and the trailing 0’s in x,|               |                   |                       |
|producing all 1’s if no 1-bit,  |               |                   |                       |
|and the integer 1 if no trailing|               |                   |                       |
|0’s                             |               |                   |                       |
|                                |               |                   |                       |
|                                |               |                   |                       |
|                                |               |                   |                       |
|                                |               |                   |                       |
|                                |               |                   |                       |
|                                |               |                   |                       |
|                                |               |                   |                       |
|                                |               |                   |                       |
|                                |               |                   |                       |
|                                |               |                   |                       |
|                                |               |                   |                       |
|                                |               |                   |                       |
|                                |               |                   |                       |
+--------------------------------+---------------+-------------------+-----------------------+
|9. to create a word with 1’s at |x ⊕ (x + 1)    |(e.g., 01010111 ⇒  |x = 17 res = 3, x = 16 |
|the positions of the rightmost  |               |00001111)          |res = 1, x = 15 res =  |
|0-bit and the trailing 1’s in x,|               |                   |31                     |
|producing all 1’s if no 0-bit,  |               |                   |                       |
|and the integer 1 if no trailing|               |                   |                       |
|1’s                             |               |                   |                       |
|                                |               |                   |                       |
|                                |               |                   |                       |
|                                |               |                   |                       |
|                                |               |                   |                       |
|                                |               |                   |                       |
|                                |               |                   |                       |
|                                |               |                   |                       |
|                                |               |                   |                       |
|                                |               |                   |                       |
|                                |               |                   |                       |
|                                |               |                   |                       |
|                                |               |                   |                       |
|                                |               |                   |                       |
|                                |               |                   |                       |
+--------------------------------+---------------+-------------------+-----------------------+
|10. to turn off the rightmost   |(((x | (x − 1))|(e.g., 01011100 ==>|                       |
|contiguous string of 1’s        |+ 1) & x), ((x |01000000)          |                       |
|                                |& −x) + x)&x   |                   |                       |
|                                |               |                   |                       |
|                                |               |Used to determine  |                       |
|                                |               |if a nonnegative   |                       |
|                                |               |integer is of the  |                       |
|                                |               |form 2j − 2k for   |                       |
|                                |               |some j ≥ k≥ 0:     |                       |
|                                |               |                   |                       |
|                                |               |                   |                       |
|                                |               |                   |                       |
|                                |               |                   |                       |
|                                |               |                   |                       |
|                                |               |                   |                       |
|                                |               |                   |                       |
|                                |               |                   |                       |
|                                |               |                   |                       |
|                                |               |                   |                       |
|                                |               |                   |                       |
+--------------------------------+---------------+-------------------+-----------------------+