001 /*
002 * Java Genetic Algorithm Library (jenetics-2.0.2).
003 * Copyright (c) 2007-2014 Franz Wilhelmstötter
004 *
005 * Licensed under the Apache License, Version 2.0 (the "License");
006 * you may not use this file except in compliance with the License.
007 * You may obtain a copy of the License at
008 *
009 * http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 *
017 * Author:
018 * Franz Wilhelmstötter (franz.wilhelmstoetter@gmx.at)
019 */
020 package org.jenetics.util;
021
022 import static java.lang.Math.min;
023
024
025 /**
026 * Some bit utils. All operation assume <a href="http://en.wikipedia.org/wiki/Endianness">
027 * <b>little-endian</b></a> byte order.
028 *
029 * <pre>
030 * Byte: 3 2 1 0
031 * | | | |
032 * Array: |11110011|10011101|01000000|00101010|
033 * | | | |
034 * Bit: 23 15 7 0
035 * </pre>
036 *
037 * @author <a href="mailto:franz.wilhelmstoetter@gmx.at">Franz Wilhelmstötter</a>
038 * @since 1.0
039 * @version 1.5 — <em>$Date: 2014-03-31 $</em>
040 */
041 public final class bit extends StaticObject {
042 private bit() {}
043
044 /**
045 * Lookup table for counting the number of set bits in a {@code byte} value.
046 */
047 private static final byte[] BIT_SET_TABLE = {
048 (byte)1, (byte)2, (byte)2, (byte)3, (byte)2, (byte)3, (byte)3, (byte)4,
049 (byte)2, (byte)3, (byte)3, (byte)4, (byte)3, (byte)4, (byte)4, (byte)5,
050 (byte)2, (byte)3, (byte)3, (byte)4, (byte)3, (byte)4, (byte)4, (byte)5,
051 (byte)3, (byte)4, (byte)4, (byte)5, (byte)4, (byte)5, (byte)5, (byte)6,
052 (byte)2, (byte)3, (byte)3, (byte)4, (byte)3, (byte)4, (byte)4, (byte)5,
053 (byte)3, (byte)4, (byte)4, (byte)5, (byte)4, (byte)5, (byte)5, (byte)6,
054 (byte)3, (byte)4, (byte)4, (byte)5, (byte)4, (byte)5, (byte)5, (byte)6,
055 (byte)4, (byte)5, (byte)5, (byte)6, (byte)5, (byte)6, (byte)6, (byte)7,
056 (byte)2, (byte)3, (byte)3, (byte)4, (byte)3, (byte)4, (byte)4, (byte)5,
057 (byte)3, (byte)4, (byte)4, (byte)5, (byte)4, (byte)5, (byte)5, (byte)6,
058 (byte)3, (byte)4, (byte)4, (byte)5, (byte)4, (byte)5, (byte)5, (byte)6,
059 (byte)4, (byte)5, (byte)5, (byte)6, (byte)5, (byte)6, (byte)6, (byte)7,
060 (byte)3, (byte)4, (byte)4, (byte)5, (byte)4, (byte)5, (byte)5, (byte)6,
061 (byte)4, (byte)5, (byte)5, (byte)6, (byte)5, (byte)6, (byte)6, (byte)7,
062 (byte)4, (byte)5, (byte)5, (byte)6, (byte)5, (byte)6, (byte)6, (byte)7,
063 (byte)5, (byte)6, (byte)6, (byte)7, (byte)6, (byte)7, (byte)7, (byte)8,
064 (byte)0, (byte)1, (byte)1, (byte)2, (byte)1, (byte)2, (byte)2, (byte)3,
065 (byte)1, (byte)2, (byte)2, (byte)3, (byte)2, (byte)3, (byte)3, (byte)4,
066 (byte)1, (byte)2, (byte)2, (byte)3, (byte)2, (byte)3, (byte)3, (byte)4,
067 (byte)2, (byte)3, (byte)3, (byte)4, (byte)3, (byte)4, (byte)4, (byte)5,
068 (byte)1, (byte)2, (byte)2, (byte)3, (byte)2, (byte)3, (byte)3, (byte)4,
069 (byte)2, (byte)3, (byte)3, (byte)4, (byte)3, (byte)4, (byte)4, (byte)5,
070 (byte)2, (byte)3, (byte)3, (byte)4, (byte)3, (byte)4, (byte)4, (byte)5,
071 (byte)3, (byte)4, (byte)4, (byte)5, (byte)4, (byte)5, (byte)5, (byte)6,
072 (byte)1, (byte)2, (byte)2, (byte)3, (byte)2, (byte)3, (byte)3, (byte)4,
073 (byte)2, (byte)3, (byte)3, (byte)4, (byte)3, (byte)4, (byte)4, (byte)5,
074 (byte)2, (byte)3, (byte)3, (byte)4, (byte)3, (byte)4, (byte)4, (byte)5,
075 (byte)3, (byte)4, (byte)4, (byte)5, (byte)4, (byte)5, (byte)5, (byte)6,
076 (byte)2, (byte)3, (byte)3, (byte)4, (byte)3, (byte)4, (byte)4, (byte)5,
077 (byte)3, (byte)4, (byte)4, (byte)5, (byte)4, (byte)5, (byte)5, (byte)6,
078 (byte)3, (byte)4, (byte)4, (byte)5, (byte)4, (byte)5, (byte)5, (byte)6,
079 (byte)4, (byte)5, (byte)5, (byte)6, (byte)5, (byte)6, (byte)6, (byte)7
080 };
081 private static final int BIT_SET_TABLE_INDEX_OFFSET = 128;
082
083 /**
084 * Return the (boolean) value of the byte array at the given bit index.
085 *
086 * @param data the byte array.
087 * @param index the bit index.
088 * @return the value at the given bit index.
089 * @throws IndexOutOfBoundsException if the index is
090 * {@code index >= max || index < 0}.
091 * @throws NullPointerException if the {@code data} array is {@code null}.
092 */
093 public static boolean get(final byte[] data, final int index) {
094 return (data[index >>> 3] & (1 << (index & 7))) != 0;
095 }
096
097 /**
098 * Set the bit in the given byte array at the bit position (not the index
099 * within the byte array) to the specified value.
100 *
101 * @param data the byte array.
102 * @param index the bit index within the byte array.
103 * @param value the value to set.
104 * @return the given data array.
105 * @throws IndexOutOfBoundsException if the index is
106 * {@code index >= max || index < 0}.
107 * @throws NullPointerException if the {@code data} array is {@code null}.
108 */
109 public static byte[] set(
110 final byte[] data,
111 final int index,
112 final boolean value
113 ) {
114 return value ? set(data, index) : unset(data, index);
115 }
116
117 /**
118 * Set the bit in the given byte array at the bit position (not the index
119 * within the byte array) to {@code true}.
120 *
121 * @param data the byte array.
122 * @param index the bit index within the byte array.
123 * @return the given data array.
124 * @throws IndexOutOfBoundsException if the index is
125 * {@code index >= max || index < 0}.
126 * @throws NullPointerException if the {@code data} array is {@code null}.
127 */
128 public static byte[] set(final byte[] data, final int index) {
129 data[index >>> 3] |= 1 << (index & 7);
130 return data;
131 }
132
133 /**
134 * Set the bit in the given byte array at the bit position (not the index
135 * within the byte array) to {@code false}.
136 *
137 * @param data the byte array.
138 * @param index the bit index within the byte array.
139 * @return the given data array.
140 * @throws IndexOutOfBoundsException if the index is
141 * {@code index >= max || index < 0}.
142 * @throws NullPointerException if the {@code data} array is {@code null}.
143 */
144 public static byte[] unset(final byte[] data, final int index) {
145 data[index >>> 3] &= ~(1 << (index & 7));
146 return data;
147 }
148
149 /**
150 * Swap a given range with a range of the same size with another array.
151 *
152 * <pre>
153 * start end
154 * | |
155 * data: +---+---+---+---+---+---+---+---+---+---+---+---+
156 * +---------------+
157 * +---------------+
158 * otherData: +---+---+---+---+---+---+---+---+---+---+---+---+
159 * |
160 * otherStart
161 * </pre>
162 *
163 * @param data the first byte array which are used for swapping.
164 * @param start the start bit index of the {@code data} byte array,
165 * inclusively.
166 * @param end the end bit index of the {@code data} byte array, exclusively.
167 * @param otherData the other byte array to swap the elements with.
168 * @param otherStart the start index of the {@code otherData} byte array.
169 * @throws IndexOutOfBoundsException if {@code start > end} or
170 * if {@code start < 0 || end >= data.length*8 || otherStart < 0 ||
171 * otherStart + (end - start) >= otherData.length*8}
172 */
173 public static void swap(
174 final byte[] data, final int start, final int end,
175 final byte[] otherData, final int otherStart
176 ) {
177 for (int i = (end - start); --i >= 0;) {
178 final boolean temp = get(data, i + start);
179 set(data, i + start, get(otherData, otherStart + i));
180 set(otherData, otherStart + i, temp);
181 }
182 }
183
184 /**
185 * Returns the number of one-bits in the given {@code byte} array.
186 *
187 * @param data the {@code byte} array for which the one bits should be
188 * counted.
189 * @return the number of one bits in the given {@code byte} array.
190 */
191 public static int count(final byte[] data) {
192 int count = 0;
193 for (int i = data.length; --i >= 0;) {
194 count += count(data[i]);
195 }
196 return count;
197 }
198
199 /**
200 * Returns the number of one-bits in the given {@code byte} {@code value}.
201 *
202 * @param value the value for which the one bits should be counted.
203 * @return the number of one bits in the given value
204 */
205 public static int count(final byte value) {
206 return BIT_SET_TABLE[value + BIT_SET_TABLE_INDEX_OFFSET];
207 }
208
209 /**
210 * Shifting all bits in the given {@code data} array the given
211 * {@code shift} to the right. The bits on the left side are filled with
212 * zeros.
213 *
214 * @param data the data bits to shift.
215 * @param shift the number of bits to shift.
216 * @return the given {@code data} array.
217 * @throws NullPointerException if the {@code data} array is {@code null}.
218 */
219 public static byte[] shiftRight(final byte[] data, final int shift) {
220 final int bytes = min(shift >>> 3, data.length);
221 final int bits = shift & 7;
222
223 if (bytes > 0) {
224 for (int i = 0, n = data.length - bytes; i < n; ++i) {
225 data[i] = data[i + bytes];
226 }
227 for (int i = data.length, n = data.length - bytes; --i >= n;) {
228 data[i] = (byte)0;
229 }
230 }
231 if (bits > 0 && bytes < data.length) {
232 int carry = 0;
233 int nextCarry = 0;
234
235 for (int i = data.length; --i >= 0;) {
236 int d = data[i] & 0xFF;
237 nextCarry = (d << (8 - bits));
238
239 d >>>= bits;
240 d |= carry;
241 data[i] = (byte)(d & 0xFF);
242
243 carry = nextCarry;
244 }
245 }
246
247 return data;
248 }
249
250 /**
251 * Shifting all bits in the given {@code data} array the given
252 * {@code shift} to the left. The bits on the right side are filled with
253 * zeros.
254 *
255 * @param data the data bits to shift.
256 * @param shift the number of bits to shift.
257 * @return the given {@code data} array.
258 * @throws NullPointerException if the {@code data} array is {@code null}.
259 */
260 public static byte[] shiftLeft(final byte[] data, final int shift) {
261 final int bytes = min(shift >>> 3, data.length);
262 final int bits = shift & 7;
263
264 if (bytes > 0) {
265 for (int i = 0, n = data.length - bytes; i < n; ++i) {
266 data[data.length - 1 - i] = data[data.length - 1 - i - bytes];
267 }
268 for (int i = 0; i < bytes; ++i) {
269 data[i] = (byte)0;
270 }
271 }
272 if (bits > 0 && bytes < data.length) {
273 int carry = 0;
274 int nextCarry = 0;
275
276 for (int i = bytes; i < data.length; ++i) {
277 int d = data[i] & 0xFF;
278 nextCarry = (d >>> (8 - bits));
279
280 d <<= bits;
281 d |= carry;
282 data[i] = (byte)(d & 0xFF);
283
284 carry = nextCarry;
285 }
286 }
287
288 return data;
289 }
290
291 /**
292 * Increment the given {@code data} array.
293 *
294 * @param data the given {@code data} array.
295 * @return the given {@code data} array.
296 * @throws NullPointerException if the {@code data} array is {@code null}.
297 */
298 public static byte[] increment(final byte[] data) {
299 boolean carry = true;
300 for (int i = 0; i < data.length && carry; ++i) {
301 data[i] = (byte)(data[i] + 1);
302 carry = data[i] > 0xFF;
303 }
304
305 return data;
306 }
307
308 /**
309 * Invert the given {@code data} array.
310 *
311 * @param data the given {@code data} array.
312 * @return the given {@code data} array.
313 * @throws NullPointerException if the {@code data} array is {@code null}.
314 */
315 public static byte[] invert(final byte[] data) {
316 for (int i = data.length; --i >= 0;) {
317 data[i] = (byte)~data[i];
318 }
319 return data;
320 }
321
322 /**
323 * Make the two's complement of the given {@code data} array.
324 *
325 * @param data the given {@code data} array.
326 * @return the given {@code data} array.
327 * @throws NullPointerException if the {@code data} array is {@code null}.
328 */
329 public static byte[] complement(final byte[] data) {
330 return increment(invert(data));
331 }
332
333 /**
334 * Flip the bit at the given index.
335 *
336 * @param data the data array.
337 * @param index the index of the bit to flip.
338 * @return the input array, for command chaining
339 * @throws IndexOutOfBoundsException if the index is
340 * {@code index >= max || index < 0}.
341 * @throws NullPointerException if the {@code data} array is {@code null}.
342 */
343 public static byte[] flip(final byte[] data, final int index) {
344 return get(data, index) ? unset(data, index) : set(data, index);
345 }
346
347 static byte[] reverse(final byte[] array) {
348 int i = 0;
349 int j = array.length;
350
351 while (i < j) {
352 swap(array, i++, --j);
353 }
354
355 return array;
356 }
357
358 private static void swap(final byte[] array, final int i, final int j) {
359 final byte temp = array[i];
360 array[i] = array[j];
361 array[j] = temp;
362 }
363
364 /**
365 * Convert a binary representation of the given byte array to a string. The
366 * string has the following format:
367 * <pre>
368 * Byte: 3 2 1 0
369 * | | | |
370 * Array: "11110011|10011101|01000000|00101010"
371 * | | | |
372 * Bit: 23 15 7 0
373 * </pre>
374 * <i>Only the array string is printed.</i>
375 *
376 * @see #fromByteString(String)
377 *
378 * @param data the byte array to convert to a string.
379 * @return the binary representation of the given byte array.
380 */
381 public static String toByteString(final byte... data) {
382 final StringBuilder out = new StringBuilder();
383
384 if (data.length > 0) {
385 for (int j = 7; j >= 0; --j) {
386 out.append((data[data.length - 1] >>> j) & 1);
387 }
388 }
389 for (int i = data.length - 2; i >= 0 ;--i) {
390 out.append('|');
391 for (int j = 7; j >= 0; --j) {
392 out.append((data[i] >>> j) & 1);
393 }
394 }
395
396 return out.toString();
397 }
398
399 /**
400 * Convert a string which was created with the {@link #toByteString(byte...)}
401 * method back to an byte array.
402 *
403 * @see #toByteString(byte...)
404 *
405 * @param data the string to convert.
406 * @return the byte array.
407 * @throws IllegalArgumentException if the given data string could not be
408 * converted.
409 */
410 public static byte[] fromByteString(final String data) {
411 final String[] parts = data.split("\\|");
412 final byte[] bytes = new byte[parts.length];
413
414 for (int i = 0; i < parts.length; ++i) {
415 if (parts[i].length() != 8) {
416 throw new IllegalArgumentException(
417 "Byte value doesn't contain 8 bit: " + parts[i]
418 );
419 }
420
421 try {
422 bytes[parts.length - 1 - i] = (byte)Integer.parseInt(parts[i], 2);
423 } catch (NumberFormatException e) {
424 throw new IllegalArgumentException(e);
425 }
426 }
427
428 return bytes;
429 }
430
431 /**
432 * Create a new {@code byte[]} array which can store at least the number
433 * of bits as defined by the given {@code length} parameter.
434 *
435 * @param length the number of bits, the returned byte array can store.
436 * @return the new byte array.s
437 */
438 public static byte[] newArray(final int length) {
439 return new byte[toByteLength(length)];
440 }
441
442 /**
443 * Create a new {@code byte[]} array which can store at least the number
444 * of bits as defined by the given {@code length} parameter. The returned
445 * byte array is initialized with ones according to the given ones
446 * probability {@code p}.
447 *
448 * @param length the number of bits, the returned byte array can store.
449 * @param p the ones probability of the returned byte array.
450 * @return the new byte array.s
451 * @throws IllegalArgumentException if {@code p} is not a valid probability.
452 */
453 public static byte[] newArray(final int length, final double p) {
454 final byte[] bytes = newArray(length);
455
456 final IndexStream stream = IndexStream.Random(length, p);
457 for (int i = stream.next(); i != -1; i = stream.next()) {
458 bytes[i >>> 3] |= 1 << (i & 7);
459 }
460
461 return bytes;
462 }
463
464 /**
465 * Return the minimum number of bytes to store the given number of bits.
466 *
467 * @param bitLength the number of bits
468 * @return the number of bytes needed to store the given number of bits.
469 */
470 public static int toByteLength(final int bitLength) {
471 return (bitLength & 7) == 0 ? (bitLength >>> 3) : (bitLength >>> 3) + 1;
472 }
473
474 static long toLong(final byte[] data) {
475 return
476 (((long)data[0] << 56) +
477 ((long)(data[1] & 255) << 48) +
478 ((long)(data[2] & 255) << 40) +
479 ((long)(data[3] & 255) << 32) +
480 ((long)(data[4] & 255) << 24) +
481 ((data[5] & 255) << 16) +
482 ((data[6] & 255) << 8) +
483 ((data[7] & 255)));
484 }
485
486 static byte[] toBytes(final long value) {
487 final byte[] bytes = new byte[8];
488 bytes[0] = (byte)(value >>> 56);
489 bytes[1] = (byte)(value >>> 48);
490 bytes[2] = (byte)(value >>> 40);
491 bytes[3] = (byte)(value >>> 32);
492 bytes[4] = (byte)(value >>> 24);
493 bytes[5] = (byte)(value >>> 16);
494 bytes[6] = (byte)(value >>> 8);
495 bytes[7] = (byte)(value);
496 return bytes;
497 }
498
499 static byte[] writeInt(final int v, final byte[] data, final int start) {
500 if (data.length < 4 + start) {
501 throw new IllegalArgumentException(
502 "Byte array to short: " + data.length
503 );
504 }
505
506 data[start] = (byte)((v >>> 24) & 0xFF);
507 data[1 + start] = (byte)((v >>> 16) & 0xFF);
508 data[2 + start] = (byte)((v >>> 8) & 0xFF);
509 data[3 + start] = (byte)((v) & 0xFF);
510
511 return data;
512 }
513
514 static int readInt(final byte[] data, final int start) {
515 if (data.length < 4 + start) {
516 throw new IllegalArgumentException(
517 "Byte array to short: " + data.length
518 );
519 }
520
521 return ((data[start] << 24) +
522 (data[1 + start] << 16) +
523 (data[2 + start] << 8) +
524 (data[3 + start]));
525 }
526
527 }
|