aboutsummaryrefslogtreecommitdiffstats
path: root/src
diff options
context:
space:
mode:
authorMattias Andrée <maandree@operamail.com>2014-01-21 06:59:01 +0100
committerMattias Andrée <maandree@operamail.com>2014-01-21 06:59:01 +0100
commite059318d6cc92b3b11b974dfe252a8c4267e6188 (patch)
treeca917118de70a2731da7cbae52eb1ec397d1f5da /src
parentm doc (diff)
downloadalgorithms-and-data-structures-e059318d6cc92b3b11b974dfe252a8c4267e6188.tar.gz
algorithms-and-data-structures-e059318d6cc92b3b11b974dfe252a8c4267e6188.tar.bz2
algorithms-and-data-structures-e059318d6cc92b3b11b974dfe252a8c4267e6188.tar.xz
bit reversing
Signed-off-by: Mattias Andrée <maandree@operamail.com>
Diffstat (limited to '')
-rw-r--r--src/algorithms/bits/Bits.java123
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
}