bit.java
/*
* Java Genetic Algorithm Library (@__identifier__@).
* Copyright (c) @__year__@ Franz Wilhelmstötter
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*
* Author:
* Franz Wilhelmstötter (franz.wilhelmstoetter@gmx.at)
*/
package org.jenetics.util;
import static java.lang.Math.min;
import org.jscience.mathematics.number.LargeInteger;
/**
* Some bit utils. All operation assume <a href="http://en.wikipedia.org/wiki/Endianness">
* <b>little-endian</b></a> byte order.
*
* <pre>
* Byte: 3 2 1 0
* | | | |
* Array: |11110011|10011101|01000000|00101010|
* | | | |
* Bit: 23 15 7 0
* </pre>
*
* @author <a href="mailto:franz.wilhelmstoetter@gmx.at">Franz Wilhelmstötter</a>
* @since 1.0
* @version 1.5 — <em>$Date: 2014-03-07 $</em>
*/
public final class bit extends StaticObject {
private bit() {}
/**
* Lookup table for counting the number of set bits in a {@code byte} value.
*/
private static final byte[] BIT_SET_TABLE = {
(byte)1, (byte)2, (byte)2, (byte)3, (byte)2, (byte)3, (byte)3, (byte)4,
(byte)2, (byte)3, (byte)3, (byte)4, (byte)3, (byte)4, (byte)4, (byte)5,
(byte)2, (byte)3, (byte)3, (byte)4, (byte)3, (byte)4, (byte)4, (byte)5,
(byte)3, (byte)4, (byte)4, (byte)5, (byte)4, (byte)5, (byte)5, (byte)6,
(byte)2, (byte)3, (byte)3, (byte)4, (byte)3, (byte)4, (byte)4, (byte)5,
(byte)3, (byte)4, (byte)4, (byte)5, (byte)4, (byte)5, (byte)5, (byte)6,
(byte)3, (byte)4, (byte)4, (byte)5, (byte)4, (byte)5, (byte)5, (byte)6,
(byte)4, (byte)5, (byte)5, (byte)6, (byte)5, (byte)6, (byte)6, (byte)7,
(byte)2, (byte)3, (byte)3, (byte)4, (byte)3, (byte)4, (byte)4, (byte)5,
(byte)3, (byte)4, (byte)4, (byte)5, (byte)4, (byte)5, (byte)5, (byte)6,
(byte)3, (byte)4, (byte)4, (byte)5, (byte)4, (byte)5, (byte)5, (byte)6,
(byte)4, (byte)5, (byte)5, (byte)6, (byte)5, (byte)6, (byte)6, (byte)7,
(byte)3, (byte)4, (byte)4, (byte)5, (byte)4, (byte)5, (byte)5, (byte)6,
(byte)4, (byte)5, (byte)5, (byte)6, (byte)5, (byte)6, (byte)6, (byte)7,
(byte)4, (byte)5, (byte)5, (byte)6, (byte)5, (byte)6, (byte)6, (byte)7,
(byte)5, (byte)6, (byte)6, (byte)7, (byte)6, (byte)7, (byte)7, (byte)8,
(byte)0, (byte)1, (byte)1, (byte)2, (byte)1, (byte)2, (byte)2, (byte)3,
(byte)1, (byte)2, (byte)2, (byte)3, (byte)2, (byte)3, (byte)3, (byte)4,
(byte)1, (byte)2, (byte)2, (byte)3, (byte)2, (byte)3, (byte)3, (byte)4,
(byte)2, (byte)3, (byte)3, (byte)4, (byte)3, (byte)4, (byte)4, (byte)5,
(byte)1, (byte)2, (byte)2, (byte)3, (byte)2, (byte)3, (byte)3, (byte)4,
(byte)2, (byte)3, (byte)3, (byte)4, (byte)3, (byte)4, (byte)4, (byte)5,
(byte)2, (byte)3, (byte)3, (byte)4, (byte)3, (byte)4, (byte)4, (byte)5,
(byte)3, (byte)4, (byte)4, (byte)5, (byte)4, (byte)5, (byte)5, (byte)6,
(byte)1, (byte)2, (byte)2, (byte)3, (byte)2, (byte)3, (byte)3, (byte)4,
(byte)2, (byte)3, (byte)3, (byte)4, (byte)3, (byte)4, (byte)4, (byte)5,
(byte)2, (byte)3, (byte)3, (byte)4, (byte)3, (byte)4, (byte)4, (byte)5,
(byte)3, (byte)4, (byte)4, (byte)5, (byte)4, (byte)5, (byte)5, (byte)6,
(byte)2, (byte)3, (byte)3, (byte)4, (byte)3, (byte)4, (byte)4, (byte)5,
(byte)3, (byte)4, (byte)4, (byte)5, (byte)4, (byte)5, (byte)5, (byte)6,
(byte)3, (byte)4, (byte)4, (byte)5, (byte)4, (byte)5, (byte)5, (byte)6,
(byte)4, (byte)5, (byte)5, (byte)6, (byte)5, (byte)6, (byte)6, (byte)7
};
private static final int BIT_SET_TABLE_INDEX_OFFSET = 128;
/**
* Return the (boolean) value of the byte array at the given bit index.
*
* @param data the byte array.
* @param index the bit index.
* @return the value at the given bit index.
* @throws IndexOutOfBoundsException if the index is
* {@code index >= max || index < 0}.
* @throws NullPointerException if the {@code data} array is {@code null}.
*/
public static boolean get(final byte[] data, final int index) {
return (data[index >>> 3] & (1 << (index & 7))) != 0;
}
/**
* Set the bit in the given byte array at the bit position (not the index
* within the byte array) to the specified value.
*
* @param data the byte array.
* @param index the bit index within the byte array.
* @param value the value to set.
* @return the given data array.
* @throws IndexOutOfBoundsException if the index is
* {@code index >= max || index < 0}.
* @throws NullPointerException if the {@code data} array is {@code null}.
*/
public static byte[] set(
final byte[] data,
final int index,
final boolean value
) {
return value ? set(data, index) : unset(data, index);
}
/**
* Set the bit in the given byte array at the bit position (not the index
* within the byte array) to {@code true}.
*
* @param data the byte array.
* @param index the bit index within the byte array.
* @return the given data array.
* @throws IndexOutOfBoundsException if the index is
* {@code index >= max || index < 0}.
* @throws NullPointerException if the {@code data} array is {@code null}.
*/
public static byte[] set(final byte[] data, final int index) {
data[index >>> 3] |= 1 << (index & 7);
return data;
}
/**
* Set the bit in the given byte array at the bit position (not the index
* within the byte array) to {@code false}.
*
* @param data the byte array.
* @param index the bit index within the byte array.
* @return the given data array.
* @throws IndexOutOfBoundsException if the index is
* {@code index >= max || index < 0}.
* @throws NullPointerException if the {@code data} array is {@code null}.
*/
public static byte[] unset(final byte[] data, final int index) {
data[index >>> 3] &= ~(1 << (index & 7));
return data;
}
/**
* Swap a given range with a range of the same size with another array.
*
* <pre>
* start end
* | |
* data: +---+---+---+---+---+---+---+---+---+---+---+---+
* +---------------+
* +---------------+
* otherData: +---+---+---+---+---+---+---+---+---+---+---+---+
* |
* otherStart
* </pre>
*
* @param data the first byte array which are used for swapping.
* @param start the start bit index of the {@code data} byte array,
* inclusively.
* @param end the end bit index of the {@code data} byte array, exclusively.
* @param otherData the other byte array to swap the elements with.
* @param otherStart the start index of the {@code otherData} byte array.
* @throws IndexOutOfBoundsException if {@code start > end} or
* if {@code start < 0 || end >= data.length*8 || otherStart < 0 ||
* otherStart + (end - start) >= otherData.length*8}
*/
public static void swap(
final byte[] data, final int start, final int end,
final byte[] otherData, final int otherStart
) {
for (int i = (end - start); --i >= 0;) {
final boolean temp = get(data, i + start);
set(data, i + start, get(otherData, otherStart + i));
set(otherData, otherStart + i, temp);
}
}
/**
* Returns the number of one-bits in the given {@code byte} array.
*
* @param data the {@code byte} array for which the one bits should be
* counted.
* @return the number of one bits in the given {@code byte} array.
*/
public static int count(final byte[] data) {
int count = 0;
for (int i = data.length; --i >= 0;) {
count += count(data[i]);
}
return count;
}
/**
* Returns the number of one-bits in the given {@code byte} {@code value}.
*
* @param value the value for which the one bits should be counted.
* @return the number of one bits in the given value
*/
public static int count(final byte value) {
return BIT_SET_TABLE[value + BIT_SET_TABLE_INDEX_OFFSET];
}
/**
* Shifting all bits in the given {@code data} array the given
* {@code shift} to the right. The bits on the left side are filled with
* zeros.
*
* @param data the data bits to shift.
* @param shift the number of bits to shift.
* @return the given {@code data} array.
* @throws NullPointerException if the {@code data} array is {@code null}.
*/
public static byte[] shiftRight(final byte[] data, final int shift) {
final int bytes = min(shift >>> 3, data.length);
final int bits = shift & 7;
if (bytes > 0) {
for (int i = 0, n = data.length - bytes; i < n; ++i) {
data[i] = data[i + bytes];
}
for (int i = data.length, n = data.length - bytes; --i >= n;) {
data[i] = (byte)0;
}
}
if (bits > 0 && bytes < data.length) {
int carry = 0;
int nextCarry = 0;
for (int i = data.length; --i >= 0;) {
int d = data[i] & 0xFF;
nextCarry = (d << (8 - bits));
d >>>= bits;
d |= carry;
data[i] = (byte)(d & 0xFF);
carry = nextCarry;
}
}
return data;
}
/**
* Shifting all bits in the given {@code data} array the given
* {@code shift} to the left. The bits on the right side are filled with
* zeros.
*
* @param data the data bits to shift.
* @param shift the number of bits to shift.
* @return the given {@code data} array.
* @throws NullPointerException if the {@code data} array is {@code null}.
*/
public static byte[] shiftLeft(final byte[] data, final int shift) {
final int bytes = min(shift >>> 3, data.length);
final int bits = shift & 7;
if (bytes > 0) {
for (int i = 0, n = data.length - bytes; i < n; ++i) {
data[data.length - 1 - i] = data[data.length - 1 - i - bytes];
}
for (int i = 0; i < bytes; ++i) {
data[i] = (byte)0;
}
}
if (bits > 0 && bytes < data.length) {
int carry = 0;
int nextCarry = 0;
for (int i = bytes; i < data.length; ++i) {
int d = data[i] & 0xFF;
nextCarry = (d >>> (8 - bits));
d <<= bits;
d |= carry;
data[i] = (byte)(d & 0xFF);
carry = nextCarry;
}
}
return data;
}
/**
* Increment the given {@code data} array.
*
* @param data the given {@code data} array.
* @return the given {@code data} array.
* @throws NullPointerException if the {@code data} array is {@code null}.
*/
public static byte[] increment(final byte[] data) {
boolean carry = true;
for (int i = 0; i < data.length && carry; ++i) {
data[i] = (byte)(data[i] + 1);
carry = data[i] > 0xFF;
}
return data;
}
/**
* Invert the given {@code data} array.
*
* @param data the given {@code data} array.
* @return the given {@code data} array.
* @throws NullPointerException if the {@code data} array is {@code null}.
*/
public static byte[] invert(final byte[] data) {
for (int i = data.length; --i >= 0;) {
data[i] = (byte)~data[i];
}
return data;
}
/**
* Make the two's complement of the given {@code data} array.
*
* @param data the given {@code data} array.
* @return the given {@code data} array.
* @throws NullPointerException if the {@code data} array is {@code null}.
*/
public static byte[] complement(final byte[] data) {
return increment(invert(data));
}
/**
* Flip the bit at the given index.
*
* @param data the data array.
* @param index the index of the bit to flip.
* @throws IndexOutOfBoundsException if the index is
* {@code index >= max || index < 0}.
* @throws NullPointerException if the {@code data} array is {@code null}.
*/
public static byte[] flip(final byte[] data, final int index) {
return get(data, index) ? unset(data, index) : set(data, index);
}
/**
* Convert the given {@link LargeInteger} value to an byte array.
*
* @see #toLargeInteger(byte[])
*
* @param value the value to convert.
* @return the byte array representing the given {@link LargeInteger}.
* @throws NullPointerException if the given value is {@code null}.
*
* @deprecated Will be removed.
*/
@Deprecated
public static byte[] toByteArray(final LargeInteger value) {
final int bytes = (value.bitLength() >>> 3) + 1;
final byte[] array = new byte[bytes];
value.toByteArray(array, 0);
return reverse(array);
}
/**
* Convert the given byte array into an {@link LargeInteger}.
*
* @see #toByteArray(LargeInteger)
*
* @param array the byte array to convert.
* @return the {@link LargeInteger} built from the given byte array.
*
* @deprecated Will be removed.
*/
@Deprecated
public static LargeInteger toLargeInteger(final byte[] array) {
return LargeInteger.valueOf(reverse(array.clone()), 0, array.length);
}
static byte[] reverse(final byte[] array) {
int i = 0;
int j = array.length;
while (i < j) {
swap(array, i++, --j);
}
return array;
}
private static void swap(final byte[] array, final int i, final int j) {
final byte temp = array[i];
array[i] = array[j];
array[j] = temp;
}
/**
* Convert a binary representation of the given byte array to a string. The
* string has the following format:
* <pre>
* Byte: 3 2 1 0
* | | | |
* Array: "11110011|10011101|01000000|00101010"
* | | | |
* Bit: 23 15 7 0
* </pre>
* <i>Only the array string is printed.</i>
*
* @see #fromByteString(String)
*
* @param data the byte array to convert to a string.
* @return the binary representation of the given byte array.
*/
public static String toByteString(final byte... data) {
final StringBuilder out = new StringBuilder();
if (data.length > 0) {
for (int j = 7; j >= 0; --j) {
out.append((data[data.length - 1] >>> j) & 1);
}
}
for (int i = data.length - 2; i >= 0 ;--i) {
out.append('|');
for (int j = 7; j >= 0; --j) {
out.append((data[i] >>> j) & 1);
}
}
return out.toString();
}
/**
* Convert a string which was created with the {@link #toByteString(byte...)}
* method back to an byte array.
*
* @see #toByteString(byte...)
*
* @param data the string to convert.
* @return the byte array.
* @throws IllegalArgumentException if the given data string could not be
* converted.
*/
public static byte[] fromByteString(final String data) {
final String[] parts = data.split("\\|");
final byte[] bytes = new byte[parts.length];
for (int i = 0; i < parts.length; ++i) {
if (parts[i].length() != 8) {
throw new IllegalArgumentException(
"Byte value doesn't contain 8 bit: " + parts[i]
);
}
try {
bytes[parts.length - 1 - i] = (byte)Integer.parseInt(parts[i], 2);
} catch (NumberFormatException e) {
throw new IllegalArgumentException(e);
}
}
return bytes;
}
/**
* Create a new {@code byte[]} array which can store at least the number
* of bits as defined by the given {@code length} parameter.
*
* @param length the number of bits, the returned byte array can store.
* @return the new byte array.s
*
* @deprecated Use {@link #newArray(int)} instead.
*/
@Deprecated
public static byte[] newBitArray(final int length) {
return newArray(length);
}
/**
* Create a new {@code byte[]} array which can store at least the number
* of bits as defined by the given {@code length} parameter.
*
* @param length the number of bits, the returned byte array can store.
* @return the new byte array.s
*/
public static byte[] newArray(final int length) {
return new byte[toByteLength(length)];
}
/**
* Create a new {@code byte[]} array which can store at least the number
* of bits as defined by the given {@code length} parameter. The returned
* byte array is initialized with ones according to the given ones
* probability {@code p}.
*
* @param length the number of bits, the returned byte array can store.
* @param p the ones probability of the returned byte array.
* @return the new byte array.s
* @throws IllegalArgumentException if {@code p} is not a valid probability.
*
* @deprecated Use {@link #newArray(int, double)} instead.
*/
@Deprecated
public static byte[] newBitArray(final int length, final double p) {
return newArray(length, p);
}
/**
* Create a new {@code byte[]} array which can store at least the number
* of bits as defined by the given {@code length} parameter. The returned
* byte array is initialized with ones according to the given ones
* probability {@code p}.
*
* @param length the number of bits, the returned byte array can store.
* @param p the ones probability of the returned byte array.
* @return the new byte array.s
* @throws IllegalArgumentException if {@code p} is not a valid probability.
*/
public static byte[] newArray(final int length, final double p) {
final byte[] bytes = newArray(length);
final IndexStream stream = IndexStream.Random(length, p);
for (int i = stream.next(); i != -1; i = stream.next()) {
bytes[i >>> 3] |= 1 << (i & 7);
}
return bytes;
}
/**
* Return the minimum number of bytes to store the given number of bits.
*
* @param bitLength the number of bits
* @return the number of bytes needed to store the given number of bits.
*/
public static int toByteLength(final int bitLength) {
return (bitLength & 7) == 0 ? (bitLength >>> 3) : (bitLength >>> 3) + 1;
}
static long toLong(final byte[] data) {
return
(((long)data[0] << 56) +
((long)(data[1] & 255) << 48) +
((long)(data[2] & 255) << 40) +
((long)(data[3] & 255) << 32) +
((long)(data[4] & 255) << 24) +
((data[5] & 255) << 16) +
((data[6] & 255) << 8) +
((data[7] & 255)));
}
static byte[] toBytes(final long value) {
final byte[] bytes = new byte[8];
bytes[0] = (byte)(value >>> 56);
bytes[1] = (byte)(value >>> 48);
bytes[2] = (byte)(value >>> 40);
bytes[3] = (byte)(value >>> 32);
bytes[4] = (byte)(value >>> 24);
bytes[5] = (byte)(value >>> 16);
bytes[6] = (byte)(value >>> 8);
bytes[7] = (byte)(value);
return bytes;
}
static byte[] writeInt(final int v, final byte[] data, final int start) {
if (data.length < 4 + start) {
throw new IllegalArgumentException(
"Byte array to short: " + data.length
);
}
data[start] = (byte)((v >>> 24) & 0xFF);
data[1 + start] = (byte)((v >>> 16) & 0xFF);
data[2 + start] = (byte)((v >>> 8) & 0xFF);
data[3 + start] = (byte)((v) & 0xFF);
return data;
}
static int readInt(final byte[] data, final int start) {
if (data.length < 4 + start) {
throw new IllegalArgumentException(
"Byte array to short: " + data.length
);
}
return ((data[start] << 24) +
(data[1 + start] << 16) +
(data[2 + start] << 8) +
(data[3 + start]));
}
}