// output of ./demo/bits/modular-lookup-demo.cc: // Description: //% Determination of the lowest bit in a word via modular arithmetic. modulus m=67 mt[k]= 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 0 0 1 39 2 15 40 23 3 12 16 59 41 19 24 54 4 64 13 10 17 62 60 28 42 30 20 51 25 44 55 47 5 32 65 38 14 22 11 58 18 53 63 9 61 27 29 50 43 46 31 37 21 57 52 8 26 49 45 36 56 7 48 35 Lowest bit == 0: x= ...............................................................1 = 1 x % m= 1 ==> lookup = 0 Lowest bit == 1: x= ..............................................................1. = 2 x % m= 2 ==> lookup = 1 Lowest bit == 2: x= .............................................................1.. = 4 x % m= 4 ==> lookup = 2 Lowest bit == 3: x= ............................................................1... = 8 x % m= 8 ==> lookup = 3 Lowest bit == 4: x= ...........................................................1.... = 16 x % m= 16 ==> lookup = 4 Lowest bit == 5: x= ..........................................................1..... = 32 x % m= 32 ==> lookup = 5 Lowest bit == 6: x= .........................................................1...... = 64 x % m= 64 ==> lookup = 6 Lowest bit == 7: x= ........................................................1....... = 128 x % m= 61 ==> lookup = 7 Lowest bit == 8: x= .......................................................1........ = 256 x % m= 55 ==> lookup = 8 Lowest bit == 9: x= ......................................................1......... = 512 x % m= 43 ==> lookup = 9 Lowest bit == 10: x= .....................................................1.......... = 1024 x % m= 19 ==> lookup = 10 Lowest bit == 11: x= ....................................................1........... = 2048 x % m= 38 ==> lookup = 11 Lowest bit == 12: x= ...................................................1............ = 4096 x % m= 9 ==> lookup = 12 Lowest bit == 13: x= ..................................................1............. = 8192 x % m= 18 ==> lookup = 13 Lowest bit == 14: x= .................................................1.............. = 16384 x % m= 36 ==> lookup = 14 Lowest bit == 15: x= ................................................1............... = 32768 x % m= 5 ==> lookup = 15 Lowest bit == 16: x= ...............................................1................ = 65536 x % m= 10 ==> lookup = 16 Lowest bit == 17: x= ..............................................1................. = 131072 x % m= 20 ==> lookup = 17 Lowest bit == 18: x= .............................................1.................. = 262144 x % m= 40 ==> lookup = 18 Lowest bit == 19: x= ............................................1................... = 524288 x % m= 13 ==> lookup = 19 Lowest bit == 20: x= ...........................................1.................... = 1048576 x % m= 26 ==> lookup = 20 Lowest bit == 21: x= ..........................................1..................... = 2097152 x % m= 52 ==> lookup = 21 Lowest bit == 22: x= .........................................1...................... = 4194304 x % m= 37 ==> lookup = 22 Lowest bit == 23: x= ........................................1....................... = 8388608 x % m= 7 ==> lookup = 23 Lowest bit == 24: x= .......................................1........................ = 16777216 x % m= 14 ==> lookup = 24 Lowest bit == 25: x= ......................................1......................... = 33554432 x % m= 28 ==> lookup = 25 Lowest bit == 26: x= .....................................1.......................... = 67108864 x % m= 56 ==> lookup = 26 Lowest bit == 27: x= ....................................1........................... = 134217728 x % m= 45 ==> lookup = 27 Lowest bit == 28: x= ...................................1............................ = 268435456 x % m= 23 ==> lookup = 28 Lowest bit == 29: x= ..................................1............................. = 536870912 x % m= 46 ==> lookup = 29 Lowest bit == 30: x= .................................1.............................. = 1073741824 x % m= 25 ==> lookup = 30 Lowest bit == 31: x= ................................1............................... = 2147483648 x % m= 50 ==> lookup = 31 Lowest bit == 32: x= ...............................1................................ = 4294967296 x % m= 33 ==> lookup = 32 Lowest bit == 33: x= ..............................1................................. = 8589934592 x % m= 66 ==> lookup = 33 Lowest bit == 34: x= .............................1.................................. = 17179869184 x % m= 65 ==> lookup = 34 Lowest bit == 35: x= ............................1................................... = 34359738368 x % m= 63 ==> lookup = 35 Lowest bit == 36: x= ...........................1.................................... = 68719476736 x % m= 59 ==> lookup = 36 Lowest bit == 37: x= ..........................1..................................... = 137438953472 x % m= 51 ==> lookup = 37 Lowest bit == 38: x= .........................1...................................... = 274877906944 x % m= 35 ==> lookup = 38 Lowest bit == 39: x= ........................1....................................... = 549755813888 x % m= 3 ==> lookup = 39 Lowest bit == 40: x= .......................1........................................ = 1099511627776 x % m= 6 ==> lookup = 40 Lowest bit == 41: x= ......................1......................................... = 2199023255552 x % m= 12 ==> lookup = 41 Lowest bit == 42: x= .....................1.......................................... = 4398046511104 x % m= 24 ==> lookup = 42 Lowest bit == 43: x= ....................1........................................... = 8796093022208 x % m= 48 ==> lookup = 43 Lowest bit == 44: x= ...................1............................................ = 17592186044416 x % m= 29 ==> lookup = 44 Lowest bit == 45: x= ..................1............................................. = 35184372088832 x % m= 58 ==> lookup = 45 Lowest bit == 46: x= .................1.............................................. = 70368744177664 x % m= 49 ==> lookup = 46 Lowest bit == 47: x= ................1............................................... = 140737488355328 x % m= 31 ==> lookup = 47 Lowest bit == 48: x= ...............1................................................ = 281474976710656 x % m= 62 ==> lookup = 48 Lowest bit == 49: x= ..............1................................................. = 562949953421312 x % m= 57 ==> lookup = 49 Lowest bit == 50: x= .............1.................................................. = 1125899906842624 x % m= 47 ==> lookup = 50 Lowest bit == 51: x= ............1................................................... = 2251799813685248 x % m= 27 ==> lookup = 51 Lowest bit == 52: x= ...........1.................................................... = 4503599627370496 x % m= 54 ==> lookup = 52 Lowest bit == 53: x= ..........1..................................................... = 9007199254740992 x % m= 41 ==> lookup = 53 Lowest bit == 54: x= .........1...................................................... = 18014398509481984 x % m= 15 ==> lookup = 54 Lowest bit == 55: x= ........1....................................................... = 36028797018963968 x % m= 30 ==> lookup = 55 Lowest bit == 56: x= .......1........................................................ = 72057594037927936 x % m= 60 ==> lookup = 56 Lowest bit == 57: x= ......1......................................................... = 144115188075855872 x % m= 53 ==> lookup = 57 Lowest bit == 58: x= .....1.......................................................... = 288230376151711744 x % m= 39 ==> lookup = 58 Lowest bit == 59: x= ....1........................................................... = 576460752303423488 x % m= 11 ==> lookup = 59 Lowest bit == 60: x= ...1............................................................ = 1152921504606846976 x % m= 22 ==> lookup = 60 Lowest bit == 61: x= ..1............................................................. = 2305843009213693952 x % m= 44 ==> lookup = 61 Lowest bit == 62: x= .1.............................................................. = 4611686018427387904 x % m= 21 ==> lookup = 62 Lowest bit == 63: x= 1............................................................... = 9223372036854775808 x % m= 42 ==> lookup = 63