diff options
| -rw-r--r-- | src/algorithms/bits/Bits.java | 123 |
1 files changed, 117 insertions, 6 deletions
diff --git a/src/algorithms/bits/Bits.java b/src/algorithms/bits/Bits.java index ace5fed..4d5c944 100644 --- a/src/algorithms/bits/Bits.java +++ b/src/algorithms/bits/Bits.java @@ -62,12 +62,35 @@ public class Bits * Lookup table for the parity of the bits in a byte */ private static byte[] PARITY_TABLE_256 = { £(parity-table 4 0) }; + + +£<function reverse-table + { + if [ $1 = 0 ]; then + if (( $2 < 128 )); then + echo -n "${2}, " + else + echo -n "$(( $2 - 256 )), " + fi + else + level=$(( $1 - 1 )) + reverse-table $level $(( $2 + 0 * 4 ** (4 - $1) )) + reverse-table $level $(( $2 + 2 * 4 ** (4 - $1) )) + reverse-table $level $(( $2 + 1 * 4 ** (4 - $1) )) + reverse-table $level $(( $2 + 3 * 4 ** (4 - $1) )) + fi +£>} + + /** + * Lookup table for the revered bit order in a byte + */ + private static byte[] REVERSE_TABLE_256 = { £(reverse-table 4 0) }; /** * Compute the parity of all bits in an integer, 64-bit multiply–modulus version * - * @param value The interger + * @param value The integer * @return The parity */ public static int parity_64bit(byte value) @@ -75,6 +98,39 @@ public class Bits return (int)(((value * 0x0101010101010101L) & 0x8040201008040201L) % 0x1FF) & 1; } + /** + * Reverse the order of all bits in an integer, 64-bit instructions version + * + * @param value The integer + * @return The integer reversed + */ + public static byte reverse_64bit(byte value) + { + return (byte)(((value * 0x0202020202L) & 0x010884422010L) % 1023); + } + + /** + * Reverse the order of all bits in an integer, division-free 64-bit instructions version + * + * @param value The integer + * @return The integer reversed + */ + public static byte reverse_64bit_noMod(byte value) + { + return (byte)(((value * 0x80200802L) & 0x0884422110L) * 0x0101010101L >> 32); + } + + /** + * Reverse the order of all bits in an integer, 32-bit instructions version + * + * @param value The integer + * @return The integer reversed + */ + public static byte reverse_32bit(byte value) + { + return (byte)(((value * 0x0802 & 0x22110) | (value * 0x8020 & 0x88440)) * 0x10101 >> 16); + } + £<for T_S in char_2 byte_1 short_2 int_4 long_8; do T=${T_S%_*} £>S=${T_S#*_} @@ -274,7 +330,7 @@ public class Bits /** * Compute the parity of all bits in an integer, naïve version * - * @param value The interger + * @param value The integer * @return The parity */ public static £{T} parity_naïve(£{T} value) @@ -291,7 +347,7 @@ public class Bits /** * Compute the parity of all bits in an integer, parallel version * - * @param value The interger + * @param value The integer * @return The parity */ public static £{T} parity_parallel(£{T} value) @@ -312,7 +368,7 @@ public class Bits /** * Compute the parity of all bits in an integer, partial lookup table version * - * @param value The interger + * @param value The integer * @return The parity */ public static byte parity_table(£{T} value) @@ -329,7 +385,7 @@ public class Bits /** * Compute the parity of all bits in an integer, optimised parallel version * - * @param value The interger + * @param value The integer * @return The parity */ public static int parity_optimised_parallel(£{T} value) @@ -347,7 +403,7 @@ public class Bits /** * Compute the parity of all bits in an integer, multiplication version * - * @param value The interger + * @param value The integer * @return The parity */ public static £{T} parity_multiplication(£{T} value) @@ -357,6 +413,61 @@ public class Bits value = (£{T})((value & (£{T})0x1111111111111111L) * (£{T})0x1111111111111111L); return (£{T})((value >> (£{S} - 4)) & 1); } + + /** + * Reverse the order of all bits in an integer, naïve version + * + * @param value The integer + * @return The integer reversed + */ + public static £{T} reverse_naïve(£{T} value) + { + int s = £{S} * 8 - 1; + £{T} rc = value; + for (value >>>= 1; value != 0; value >>>= 1) + { + rc <<= 1; + rc |= value & 1; + s--; + } + return (£{T})(rc << s); + } + + /** + * Reverse the order of all bits in an integer, parallel version + * + * @param value The integer + * @return The integer reversed + */ + public static £{T} reverse_parallel(£{T} value) + { + value = (£{T})(((value & (£{T})0x5555555555555555L) << 1) | ((value >> 1) & (£{T})0x5555555555555555L)); + value = (£{T})(((value & (£{T})0x3333333333333333L) << 2) | ((value >> 2) & (£{T})0x3333333333333333L)); + value = (£{T})(((value & (£{T})0x0F0F0F0F0F0F0F0FL) << 4) | ((value >> 4) & (£{T})0x0F0F0F0F0F0F0F0FL)); +£>(( $S > 1 )) && + value = (£{T})(((value & (£{T})0x00FF00FF00FF00FFL) << 8) | ((value >> 8) & (£{T})0x00FF00FF00FF00FFL)); +£>(( $S > 2 )) && + value = (£{T})(((value & (£{T})0x0000FFFF0000FFFFL) << 16) | ((value >> 16) & (£{T})0x0000FFFF0000FFFFL)); +£>(( $S > 4 )) && + value = (£{T})(((value & (£{T})0x00000000FFFFFFFFL) << 32) | ((value >> 32) & (£{T})0x00000000FFFFFFFFL)); + return value; + } + + /** + * Reverse the order of all bits in an integer, partial lookup table version + * + * @param value The integer + * @return The integer reversed + */ + public static £{T} reverse_table(£{T} value) + { +£>function _ { echo "(${T})(REVERSE_TABLE_256[(int)((value >> $1) & 255)] << $2)" ; } + £{T} rc = 0; +£>for s in `seq 0 8 $(( $S - 8 ))`; do + rc |= £(_ $s "($S - 8 - $s)"); +£>done + return rc; + } £>done } |