bit.java
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 &mdash; <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(<< (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|= << (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&= ~(<< (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 > && bytes < data.length) {
232             int carry = 0;
233             int nextCarry = 0;
234 
235             for (int i = data.length; --i >= 0;) {
236                 int d = data[i0xFF;
237                 nextCarry = (d << (- 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 - - i= data[data.length - - i - bytes];
267             }
268             for (int i = 0; i < bytes; ++i) {
269                 data[i(byte)0;
270             }
271         }
272         if (bits > && 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[i0xFF;
278                 nextCarry = (d >>> (- 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[i1);
302             carry = data[i0xFF;
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>>> j1);
387             }
388         }
389         for (int i = data.length - 2; i >= ;--i) {
390             out.append('|');
391             for (int j = 7; j >= 0; --j) {
392                 out.append((data[i>>> j1);
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 - - 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|= << (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== (bitLength >>> 3(bitLength >>> 31;
472     }
473 
474     static long toLong(final byte[] data) {
475         return
476             (((long)data[0<< 56+
477             ((long)(data[1255<< 48+
478             ((long)(data[2255<< 40+
479             ((long)(data[3255<< 32+
480             ((long)(data[4255<< 24+
481             ((data[5255<< 16+
482             ((data[6255<<  8+
483             ((data[7255)));
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 < + start) {
501             throw new IllegalArgumentException(
502                 "Byte array to short: " + data.length
503             );
504         }
505 
506         data[start]     (byte)((v >>> 240xFF);
507         data[+ start(byte)((v >>> 160xFF);
508         data[+ start(byte)((v >>>  80xFF);
509         data[+ start(byte)((v)        0xFF);
510 
511         return data;
512     }
513 
514     static int readInt(final byte[] data, final int start) {
515         if (data.length < + start) {
516             throw new IllegalArgumentException(
517                 "Byte array to short: " + data.length
518             );
519         }
520 
521         return ((data[start]     << 24+
522                 (data[+ start<< 16+
523                 (data[+ start<< 8+
524                 (data[+ start]));
525     }
526 
527 }