/**
* Copyright © 2014 Mattias Andrée (m@maandree.se)
*
* This program is free software: you can redistribute it and/or modify
* it under the terms of the GNU Affero General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU Affero General Public License for more details.
*
* You should have received a copy of the GNU Affero General Public License
* along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
package algorithms.bits;
/**
* Operations on individual bits
*/
public class Bits
{
£<function ones-table
{
if [ $1 = 0 ]; then
echo -n "${2}, "
else
level=$(( $1 - 1 ))
ones-table $level $(( $2 + 0 ))
ones-table $level $(( $2 + 1 ))
ones-table $level $(( $2 + 1 ))
ones-table $level $(( $2 + 2 ))
fi
£>}
/**
* Lookup table for the number of set bits in a byte
*/
private static byte[] ONES_TABLE_256 = { £(ones-table 4 0) };
/* ONES_TABLE_256[0] = 0;
* for (int i = 0; i < 256; i++)
* ONES_TABLE_256[i] = (i & 1) + ONES_TABLE_256[i / 2];
*/
£<function parity-table
{
if [ $1 = 0 ]; then
echo -n "${2}, "
else
level=$(( $1 - 1 ))
parity-table $level $(( $2 ^ 0 ))
parity-table $level $(( $2 ^ 1 ))
parity-table $level $(( $2 ^ 1 ))
parity-table $level $(( $2 ^ 0 ))
fi
£>}
/**
* 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 integer
* @return The parity
*/
public static int parity_64bit(byte value)
{
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#*_}
/**
* Sets or clears individual bits in an integer
*
* @param value The value to modify
* @param mask Mask of bits to modify
* @param flag 1 if the bit should be set, 0 if the bit should be clears
* @return The value with the bits modified
*/
public static £{T} set_clear(£{T} value, £{T} mask, £{T} flag)
{
return (£{T})(value ^ ((-flag ^ value) & mask));
}
/**
* Sets or clears individual bits in an integer, superscalar version
*
* @param value The value to modify
* @param mask Mask of bits to modify
* @param flag 1 if the bit should be set, 0 if the bit should be clears
* @return The value with the bits modified
*/
public static £{T} set_clear_superscalar(£{T} value, £{T} mask, £{T} flag)
{
return (£{T})((value & ~mask) | (-flag & mask));
}
/**
* Merge bits from two values
*
* @param zero Integer whose bits should be kept where the mask has zeroes
* @param one Integer whose bits should be kept where the mask has onces
* @param mask The merge mask
* @return {@code (zero & ~mask) | (one & mask)}
*/
public static £{T} merge(£{T} zero, £{T} one, £{T} mask)
{
return (£{T})(zero ^ ((£{T})(zero ^ one) & mask));
}
/**
* Clears the least significant bit set
*
* @param value The integer
* @return The value with its least significant set bit cleared
*/
public static £{T} clearLeastSignificant(£{T} value)
{
return (£{T})(value & (value - 1));
}
/**
* Calculate the number of set bits in an integer, naïve version
*
* @param value The integer
* @return The number of set bits
*/
public static £{T} ones_naïve(£{T} value)
{
£{T} count = 0;
for (; value != 0; value >>>= 1)
count += (£{T})(value & 1);
return count;
}
/**
* Calculate the number of set bits in an integer, Wegner's version
*
* @param value The integer
* @return The number of set bits
*/
public static £{T} ones_wegner(£{T} value)
{
£{T} count = 0;
for (; value != 0; count++)
value &= value - 1; /* clear the least significant bit set */
return count;
}
/**
* Calculate the number of set bits in an integer, partial lookup table version
*
* @param value The integer
* @return The number of set bits
*/
public static byte ones_table(£{T} value)
{
£>function _ { echo "ONES_TABLE_256[(int)((value >> $1) & 255)]" ; }
return (byte)((byte)(£(_ 0) + £(_ 8)) + (byte)(£(_ 16) + £(_ 24)));
/* In C you can split the value by getting the address of the
value and cast the pointer to char*, that is however slower. */
}
/**
* Calculate the number of set bits in an integer, 64-bits instructions version
*
* @param value The integer
* @return The number of set bits
*/
public static long ones_64bits(£{T} value)
{
long v = value, rc;
£>(( $S > 1 )) &&
if ((v & (1L << 14L) - 1L) == v)
{
rc = (v * 0x200040008001L & 0x111111111111111L) % 0xF;
}
£>if (( $S >= 2 )); then
else
£>(( $S > 3 )) &&
if ((v & (1L << 24L) - 1L) == v)
{
rc = ((v & 0xFFF) * 0x1001001001001L & 0x84210842108421L) % 0x1F;
rc += (((v & 0XFFF000) >> 12) * 0x1001001001001L & 0x84210842108421L) % 0x1F;
}
£>if (( $S > 3 )); then
else
£>(( $S > 4 )) &&
if ((v & (1L << 32L) - 1L) == v)
{
rc = ((v & 0xFFF) * 0x1001001001001L & 0x84210842108421L) % 0x1F;
rc += (((v & 0xFFF000) >> 12) * 0x1001001001001L & 0x84210842108421L) % 0x1F;
rc += ((v >> 24) * 0x1001001001001L & 0x84210842108421L) % 0x1F;
}
£>if (( $S > 4 )); then
else
{
rc = ones_64bits(v & (1L << 32L) - 1L);
rc += ones_64bits(v >>> 32);
}
£>fi;fi;fi
return rc;
}
/**
* Calculate the number of set bits in an integer, naïve parallel version
*
* @param value The integer
* @return The number of set bits
*/
public static £{T} ones_parallel(£{T} value)
{
£{T} rc = value;
rc = (£{T})(((rc >> 1) & (£{T})0x5555555555555555L) + (rc & (£{T})0x5555555555555555L));
rc = (£{T})(((rc >> 2) & (£{T})0x3333333333333333L) + (rc & (£{T})0x3333333333333333L));
rc = (£{T})(((rc >> 4) & (£{T})0x0F0F0F0F0F0F0F0FL) + (rc & (£{T})0x0F0F0F0F0F0F0F0FL));
£>(( $S > 1 )) &&
rc = (£{T})(((rc >> 8) & (£{T})0x00FF00FF00FF00FFL) + (rc & (£{T})0x00FF00FF00FF00FFL));
£>(( $S > 2 )) &&
rc = (£{T})(((rc >> 16) & (£{T})0x0000FFFF0000FFFFL) + (rc & (£{T})0x0000FFFF0000FFFFL));
£>(( $S > 4 )) &&
rc = (£{T})(((rc >> 32) & (£{T})0x00000000FFFFFFFFL) + (rc & (£{T})0x00000000FFFFFFFFL));
return rc;
}
/**
* Calculate the number of set bits in an integer, optimised parallel version
*
* Note tha this algorithm is optimised in the number of high-level operations
* and may be a bit slow than the non-optmised version.
*
* @param value The integer
* @return The number of set bits
*/
public static £{T} ones_optimised_parallel(£{T} value)
{
£{T} rc = (£{T})(value - ((value >> 1) & (£{T})0x5555555555555555L));
rc = (£{T})(((rc >> 2) & (£{T})0x3333333333333333L) + (rc & (£{T})0x3333333333333333L));
rc = (£{T})(((rc >> 4) + rc) & (£{T})0x0F0F0F0F0F0F0F0FL);
£>(( $S > 1 )) &&
rc = (£{T})(((rc >> 8) + rc) & (£{T})0x00FF00FF00FF00FFL);
£>(( $S > 2 )) &&
rc = (£{T})(((rc >> 16) + rc) & (£{T})0x0000FFFF0000FFFFL);
£>(( $S > 4 )) &&
rc = (£{T})(((rc >> 32) + rc) & (£{T})0x00000000FFFFFFFFL);
return rc;
}
/**
* Calculate the number of set bits in an integer, parallel–64bits-like hybrid version, probably the best version
*
* @param value The integer
* @return The number of set bits
*/
public static £{T} ones_hybrid(£{T} value)
{
£>L1="($T)$(bc <<< "(256^$S - 1) / 3")L"
£>L2="($T)$(bc <<< "(256^$S - 1) / 15 * 3")L"
£>L3="($T)$(bc <<< "(256^$S - 1) / 255 * 15")L"
£>L4="($T)$(bc <<< "(256^$S - 1) / 255")L"
value -= (value >> 1) & £{L1};
value = (£{T})((value & £{L2}) + ((value >> 2) & £{L2}));
value = (£{T})((value + (value >> 4)) & £{L3});
value = (£{T})((value * £{L4}) >> ((£{S} - 1) * 8));
return value; /* Only applicable upto 128 bits */
}
/**
* Compute the parity of all bits in an integer, naïve version
*
* @param value The integer
* @return The parity
*/
public static £{T} parity_naïve(£{T} value)
{
£{T} rc = 0;
while (value != 0)
{
rc ^= 1;
value &= value - 1;
}
return rc;
}
/**
* Compute the parity of all bits in an integer, parallel version
*
* @param value The integer
* @return The parity
*/
public static £{T} parity_parallel(£{T} value)
{
£>(( $S > 4 )) &&
value ^= value >> 32;
£>(( $S > 2 )) &&
value ^= value >> 16;
£>(( $S > 1 )) &&
value ^= value >> 8;
value ^= value >> 4;
value ^= value >> 3;
value ^= value >> 2;
value ^= value >> 1;
return (£{T})(value & 1);
}
/**
* Compute the parity of all bits in an integer, partial lookup table version
*
* @param value The integer
* @return The parity
*/
public static byte parity_table(£{T} value)
{
£>(( $S > 4 )) &&
value ^= value >> 32;
£>(( $S > 2 )) &&
value ^= value >> 16;
£>(( $S > 1 )) &&
value ^= value >> 8;
return PARITY_TABLE_256[(int)value];
}
/**
* Compute the parity of all bits in an integer, optimised parallel version
*
* @param value The integer
* @return The parity
*/
public static int parity_optimised_parallel(£{T} value)
{
£>(( $S > 4 )) &&
value ^= value >> 32;
£>(( $S > 2 )) &&
value ^= value >> 16;
£>(( $S > 1 )) &&
value ^= value >> 8;
value ^= value >> 4;
return (0x6996 >> (value & 15)) & 1;
}
/**
* Compute the parity of all bits in an integer, multiplication version
*
* @param value The integer
* @return The parity
*/
public static £{T} parity_multiplication(£{T} value)
{
value ^= value >> 1;
value ^= value >> 2;
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
}
