bit.java
001 /*
002  * Java Genetic Algorithm Library (jenetics-1.6.0).
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 import org.jscience.mathematics.number.LargeInteger;
025 
026 
027 /**
028  * Some bit utils. All operation assume <a href="http://en.wikipedia.org/wiki/Endianness">
029  <b>little-endian</b></a> byte order.
030  *
031  <pre>
032  *  Byte:       3        2        1        0
033  *              |        |        |        |
034  *  Array: |11110011|10011101|01000000|00101010|
035  *          |                 |        |      |
036  *  Bit:    23                15       7      0
037  </pre>
038  *
039  @author <a href="mailto:franz.wilhelmstoetter@gmx.at">Franz Wilhelmstötter</a>
040  @since 1.0
041  @version 1.5 &mdash; <em>$Date: 2014-03-07 $</em>
042  */
043 public final class bit extends StaticObject {
044     private bit() {}
045 
046     /**
047      * Lookup table for counting the number of set bits in a {@code byte} value.
048      */
049     private static final byte[] BIT_SET_TABLE = {
050         (byte)1(byte)2(byte)2(byte)3(byte)2(byte)3(byte)3(byte)4,
051         (byte)2(byte)3(byte)3(byte)4(byte)3(byte)4(byte)4(byte)5,
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)2(byte)3(byte)3(byte)4(byte)3(byte)4(byte)4(byte)5,
055         (byte)3(byte)4(byte)4(byte)5(byte)4(byte)5(byte)5(byte)6,
056         (byte)3(byte)4(byte)4(byte)5(byte)4(byte)5(byte)5(byte)6,
057         (byte)4(byte)5(byte)5(byte)6(byte)5(byte)6(byte)6(byte)7,
058         (byte)2(byte)3(byte)3(byte)4(byte)3(byte)4(byte)4(byte)5,
059         (byte)3(byte)4(byte)4(byte)5(byte)4(byte)5(byte)5(byte)6,
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)3(byte)4(byte)4(byte)5(byte)4(byte)5(byte)5(byte)6,
063         (byte)4(byte)5(byte)5(byte)6(byte)5(byte)6(byte)6(byte)7,
064         (byte)4(byte)5(byte)5(byte)6(byte)5(byte)6(byte)6(byte)7,
065         (byte)5(byte)6(byte)6(byte)7(byte)6(byte)7(byte)7(byte)8,
066         (byte)0(byte)1(byte)1(byte)2(byte)1(byte)2(byte)2(byte)3,
067         (byte)1(byte)2(byte)2(byte)3(byte)2(byte)3(byte)3(byte)4,
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)1(byte)2(byte)2(byte)3(byte)2(byte)3(byte)3(byte)4,
071         (byte)2(byte)3(byte)3(byte)4(byte)3(byte)4(byte)4(byte)5,
072         (byte)2(byte)3(byte)3(byte)4(byte)3(byte)4(byte)4(byte)5,
073         (byte)3(byte)4(byte)4(byte)5(byte)4(byte)5(byte)5(byte)6,
074         (byte)1(byte)2(byte)2(byte)3(byte)2(byte)3(byte)3(byte)4,
075         (byte)2(byte)3(byte)3(byte)4(byte)3(byte)4(byte)4(byte)5,
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)2(byte)3(byte)3(byte)4(byte)3(byte)4(byte)4(byte)5,
079         (byte)3(byte)4(byte)4(byte)5(byte)4(byte)5(byte)5(byte)6,
080         (byte)3(byte)4(byte)4(byte)5(byte)4(byte)5(byte)5(byte)6,
081         (byte)4(byte)5(byte)5(byte)6(byte)5(byte)6(byte)6(byte)7
082     };
083     private static final int BIT_SET_TABLE_INDEX_OFFSET = 128;
084 
085     /**
086      * Return the (boolean) value of the byte array at the given bit index.
087      *
088      @param data the byte array.
089      @param index the bit index.
090      @return the value at the given bit index.
091      @throws IndexOutOfBoundsException if the index is
092      *          {@code index >= max || index < 0}.
093      @throws NullPointerException if the {@code data} array is {@code null}.
094      */
095     public static boolean get(final byte[] data, final int index) {
096         return (data[index >>> 3(<< (index & 7))) != 0;
097     }
098 
099     /**
100      * Set the bit in the given byte array at the bit position (not the index
101      * within the byte array) to the specified value.
102      *
103      @param data the byte array.
104      @param index the bit index within the byte array.
105      @param value the value to set.
106      @return the given data array.
107      @throws IndexOutOfBoundsException if the index is
108      *         {@code index >= max || index < 0}.
109      @throws NullPointerException if the {@code data} array is {@code null}.
110      */
111     public static byte[] set(
112         final byte[] data,
113         final int index,
114         final boolean value
115     ) {
116         return value ? set(data, index: unset(data, index);
117     }
118 
119     /**
120      * Set the bit in the given byte array at the bit position (not the index
121      * within the byte array) to {@code true}.
122      *
123      @param data the byte array.
124      @param index the bit index within the byte array.
125      @return the given data array.
126      @throws IndexOutOfBoundsException if the index is
127      *          {@code index >= max || index < 0}.
128      @throws NullPointerException if the {@code data} array is {@code null}.
129      */
130     public static byte[] set(final byte[] data, final int index) {
131         data[index >>> 3|= << (index & 7);
132         return data;
133     }
134 
135     /**
136      * Set the bit in the given byte array at the bit position (not the index
137      * within the byte array) to {@code false}.
138      *
139      @param data the byte array.
140      @param index the bit index within the byte array.
141      @return the given data array.
142      @throws IndexOutOfBoundsException if the index is
143      *          {@code index >= max || index < 0}.
144      @throws NullPointerException if the {@code data} array is {@code null}.
145      */
146     public static byte[] unset(final byte[] data, final int index) {
147         data[index >>> 3&= ~(<< (index & 7));
148         return data;
149     }
150 
151     /**
152      * Swap a given range with a range of the same size with another array.
153      *
154      <pre>
155      *                start            end
156      *                  |               |
157      * data:      +---+---+---+---+---+---+---+---+---+---+---+---+
158      *              +---------------+
159      *                              +---------------+
160      * otherData: +---+---+---+---+---+---+---+---+---+---+---+---+
161      *                              |
162      *                          otherStart
163      </pre>
164      *
165      @param data the first byte array which are used for swapping.
166      @param start the start bit index of the {@code data} byte array,
167      *        inclusively.
168      @param end the end bit index of the {@code data} byte array, exclusively.
169      @param otherData the other byte array to swap the elements with.
170      @param otherStart the start index of the {@code otherData} byte array.
171      @throws IndexOutOfBoundsException if {@code start > end} or
172      *         if {@code start < 0 || end >= data.length*8 || otherStart < 0 ||
173      *         otherStart + (end - start) >= otherData.length*8}
174      */
175     public static void swap(
176         final byte[] data, final int start, final int end,
177         final byte[] otherData, final int otherStart
178     ) {
179         for (int i = (end - start); --i >= 0;) {
180             final boolean temp = get(data, i + start);
181             set(data, i + start, get(otherData, otherStart + i));
182             set(otherData, otherStart + i, temp);
183         }
184     }
185 
186     /**
187      * Returns the number of one-bits in the given {@code byte} array.
188      *
189      @param data the {@code byte} array for which the one bits should be
190      *        counted.
191      @return the number of one bits in the given {@code byte} array.
192      */
193     public static int count(final byte[] data) {
194         int count = 0;
195         for (int i = data.length; --i >= 0;) {
196             count += count(data[i]);
197         }
198         return count;
199     }
200 
201     /**
202      * Returns the number of one-bits in the given {@code byte} {@code value}.
203      *
204      @param value the value for which the one bits should be counted.
205      @return the number of one bits in the given value
206      */
207     public static int count(final byte value) {
208         return BIT_SET_TABLE[value + BIT_SET_TABLE_INDEX_OFFSET];
209     }
210 
211     /**
212      * Shifting all bits in the given {@code data} array the given
213      * {@code shift} to the right. The bits on the left side are filled with
214      * zeros.
215      *
216      @param data the data bits to shift.
217      @param shift the number of bits to shift.
218      @return the given {@code data} array.
219      @throws NullPointerException if the {@code data} array is {@code null}.
220      */
221     public static byte[] shiftRight(final byte[] data, final int shift) {
222         final int bytes = min(shift >>> 3, data.length);
223         final int bits = shift & 7;
224 
225         if (bytes > 0) {
226             for (int i = 0, n = data.length - bytes; i < n; ++i) {
227                 data[i= data[i + bytes];
228             }
229             for (int i = data.length, n = data.length - bytes; --i >= n;) {
230                 data[i(byte)0;
231             }
232         }
233         if (bits > && bytes < data.length) {
234             int carry = 0;
235             int nextCarry = 0;
236 
237             for (int i = data.length; --i >= 0;) {
238                 int d = data[i0xFF;
239                 nextCarry = (d << (- bits));
240 
241                 d >>>= bits;
242                 d |= carry;
243                 data[i(byte)(d & 0xFF);
244 
245                 carry = nextCarry;
246             }
247         }
248 
249         return data;
250     }
251 
252     /**
253      * Shifting all bits in the given {@code data} array the given
254      * {@code shift} to the left. The bits on the right side are filled with
255      * zeros.
256      *
257      @param data the data bits to shift.
258      @param shift the number of bits to shift.
259      @return the given {@code data} array.
260      @throws NullPointerException if the {@code data} array is {@code null}.
261      */
262     public static byte[] shiftLeft(final byte[] data, final int shift) {
263         final int bytes = min(shift >>> 3, data.length);
264         final int bits = shift & 7;
265 
266         if (bytes > 0) {
267             for (int i = 0, n = data.length - bytes; i < n; ++i) {
268                 data[data.length - - i= data[data.length - - i - bytes];
269             }
270             for (int i = 0; i < bytes; ++i) {
271                 data[i(byte)0;
272             }
273         }
274         if (bits > && bytes < data.length) {
275             int carry = 0;
276             int nextCarry = 0;
277 
278             for (int i = bytes; i < data.length; ++i) {
279                 int d = data[i0xFF;
280                 nextCarry = (d >>> (- bits));
281 
282                 d <<= bits;
283                 d |= carry;
284                 data[i(byte)(d & 0xFF);
285 
286                 carry = nextCarry;
287             }
288         }
289 
290         return data;
291     }
292 
293     /**
294      * Increment the given {@code data} array.
295      *
296      @param data the given {@code data} array.
297      @return the given {@code data} array.
298      @throws NullPointerException if the {@code data} array is {@code null}.
299      */
300     public static byte[] increment(final byte[] data) {
301         boolean carry = true;
302         for (int i = 0; i < data.length && carry; ++i) {
303             data[i(byte)(data[i1);
304             carry = data[i0xFF;
305         }
306 
307         return data;
308     }
309 
310     /**
311      * Invert the given {@code data} array.
312      *
313      @param data the given {@code data} array.
314      @return the given {@code data} array.
315      @throws NullPointerException if the {@code data} array is {@code null}.
316      */
317     public static byte[] invert(final byte[] data)    {
318         for (int i = data.length; --i >= 0;) {
319             data[i(byte)~data[i];
320         }
321         return data;
322     }
323 
324     /**
325      * Make the two's complement of the given {@code data} array.
326      *
327      @param data the given {@code data} array.
328      @return the given {@code data} array.
329      @throws NullPointerException if the {@code data} array is {@code null}.
330      */
331     public static byte[] complement(final byte[] data) {
332         return increment(invert(data));
333     }
334 
335     /**
336      * Flip the bit at the given index.
337      *
338      @param data the data array.
339      @param index the index of the bit to flip.
340      @throws IndexOutOfBoundsException if the index is
341      *          {@code index >= max || index < 0}.
342      @throws NullPointerException if the {@code data} array is {@code null}.
343      */
344     public static byte[] flip(final byte[] data, final int index) {
345         return get(data, index? unset(data, index: set(data, index);
346     }
347 
348     /**
349      * Convert the given {@link LargeInteger} value to an byte array.
350      *
351      @see #toLargeInteger(byte[])
352      *
353      @param value the value to convert.
354      @return the byte array representing the given {@link LargeInteger}.
355      @throws NullPointerException if the given value is {@code null}.
356      *
357      @deprecated Will be removed.
358      */
359     @Deprecated
360     public static byte[] toByteArray(final LargeInteger value) {
361         final int bytes = (value.bitLength() >>> 31;
362 
363         final byte[] array = new byte[bytes];
364         value.toByteArray(array, 0);
365         return reverse(array);
366     }
367 
368     /**
369      * Convert the given byte array into an {@link LargeInteger}.
370      *
371      @see #toByteArray(LargeInteger)
372      *
373      @param array the byte array to convert.
374      @return the {@link LargeInteger} built from the given byte array.
375      *
376      @deprecated Will be removed.
377      */
378     @Deprecated
379     public static LargeInteger toLargeInteger(final byte[] array) {
380         return LargeInteger.valueOf(reverse(array.clone())0, array.length);
381     }
382 
383 
384     static byte[] reverse(final byte[] array) {
385         int i = 0;
386         int j = array.length;
387 
388         while (i < j) {
389             swap(array, i++, --j);
390         }
391 
392         return array;
393     }
394 
395     private static void swap(final byte[] array, final int i, final int j) {
396         final byte temp = array[i];
397         array[i= array[j];
398         array[j= temp;
399     }
400 
401     /**
402      * Convert a binary representation of the given byte array to a string. The
403      * string has the following format:
404      <pre>
405      *  Byte:       3        2        1        0
406      *              |        |        |        |
407      *  Array: "11110011|10011101|01000000|00101010"
408      *          |                 |        |      |
409      *  Bit:    23                15       7      0
410      </pre>
411      <i>Only the array string is printed.</i>
412      *
413      @see #fromByteString(String)
414      *
415      @param data the byte array to convert to a string.
416      @return the binary representation of the given byte array.
417      */
418     public static String toByteString(final byte... data) {
419         final StringBuilder out = new StringBuilder();
420 
421         if (data.length > 0) {
422             for (int j = 7; j >= 0; --j) {
423                 out.append((data[data.length - 1>>> j1);
424             }
425         }
426         for (int i = data.length - 2; i >= ;--i) {
427             out.append('|');
428             for (int j = 7; j >= 0; --j) {
429                 out.append((data[i>>> j1);
430             }
431         }
432 
433         return out.toString();
434     }
435 
436     /**
437      * Convert a string which was created with the {@link #toByteString(byte...)}
438      * method back to an byte array.
439      *
440      @see #toByteString(byte...)
441      *
442      @param data the string to convert.
443      @return the byte array.
444      @throws IllegalArgumentException if the given data string could not be
445      *          converted.
446      */
447      public static byte[] fromByteString(final String data) {
448         final String[] parts = data.split("\\|");
449         final byte[] bytes = new byte[parts.length];
450 
451         for (int i = 0; i < parts.length; ++i) {
452             if (parts[i].length() != 8) {
453                 throw new IllegalArgumentException(
454                     "Byte value doesn't contain 8 bit: " + parts[i]
455                 );
456             }
457 
458             try {
459                 bytes[parts.length - - i(byte)Integer.parseInt(parts[i]2);
460             catch (NumberFormatException e) {
461                 throw new IllegalArgumentException(e);
462             }
463         }
464 
465         return bytes;
466     }
467 
468     /**
469      * Create a new {@code byte[]} array which can store at least the number
470      * of bits as defined by the given {@code length} parameter.
471      *
472      @param length the number of bits, the returned byte array can store.
473      @return the new byte array.s
474      *
475      @deprecated Use {@link #newArray(int)} instead.
476      */
477     @Deprecated
478     public static byte[] newBitArray(final int length) {
479         return newArray(length);
480     }
481 
482     /**
483      * Create a new {@code byte[]} array which can store at least the number
484      * of bits as defined by the given {@code length} parameter.
485      *
486      @param length the number of bits, the returned byte array can store.
487      @return the new byte array.s
488      */
489     public static byte[] newArray(final int length) {
490         return new byte[toByteLength(length)];
491     }
492 
493     /**
494      * Create a new {@code byte[]} array which can store at least the number
495      * of bits as defined by the given {@code length} parameter. The returned
496      * byte array is initialized with ones according to the given ones
497      * probability {@code p}.
498      *
499      @param length the number of bits, the returned byte array can store.
500      @param p the ones probability of the returned byte array.
501      @return the new byte array.s
502      @throws IllegalArgumentException if {@code p} is not a valid probability.
503      *
504      @deprecated Use {@link #newArray(int, double)} instead.
505      */
506     @Deprecated
507     public static byte[] newBitArray(final int length, final double p) {
508         return newArray(length, p);
509     }
510 
511     /**
512      * Create a new {@code byte[]} array which can store at least the number
513      * of bits as defined by the given {@code length} parameter. The returned
514      * byte array is initialized with ones according to the given ones
515      * probability {@code p}.
516      *
517      @param length the number of bits, the returned byte array can store.
518      @param p the ones probability of the returned byte array.
519      @return the new byte array.s
520      @throws IllegalArgumentException if {@code p} is not a valid probability.
521      */
522     public static byte[] newArray(final int length, final double p) {
523         final byte[] bytes = newArray(length);
524 
525         final IndexStream stream = IndexStream.Random(length, p);
526         for (int i = stream.next(); i != -1; i = stream.next()) {
527             bytes[i >>> 3|= << (i & 7);
528         }
529 
530         return bytes;
531     }
532 
533     /**
534      * Return the minimum number of bytes to store the given number of bits.
535      *
536      @param bitLength the number of bits
537      @return the number of bytes needed to store the given number of bits.
538      */
539     public static int toByteLength(final int bitLength) {
540         return (bitLength & 7== (bitLength >>> 3(bitLength >>> 31;
541     }
542 
543     static long toLong(final byte[] data) {
544         return
545             (((long)data[0<< 56+
546             ((long)(data[1255<< 48+
547             ((long)(data[2255<< 40+
548             ((long)(data[3255<< 32+
549             ((long)(data[4255<< 24+
550             ((data[5255<< 16+
551             ((data[6255<<  8+
552             ((data[7255)));
553     }
554 
555     static byte[] toBytes(final long value) {
556         final byte[] bytes = new byte[8];
557         bytes[0(byte)(value >>> 56);
558         bytes[1(byte)(value >>> 48);
559         bytes[2(byte)(value >>> 40);
560         bytes[3(byte)(value >>> 32);
561         bytes[4(byte)(value >>> 24);
562         bytes[5(byte)(value >>> 16);
563         bytes[6(byte)(value >>>  8);
564         bytes[7(byte)(value);
565         return bytes;
566     }
567 
568     static byte[] writeInt(final int v, final byte[] data, final int start) {
569         if (data.length < + start) {
570             throw new IllegalArgumentException(
571                 "Byte array to short: " + data.length
572             );
573         }
574 
575         data[start]     (byte)((v >>> 240xFF);
576         data[+ start(byte)((v >>> 160xFF);
577         data[+ start(byte)((v >>>  80xFF);
578         data[+ start(byte)((v)        0xFF);
579 
580         return data;
581     }
582 
583     static int readInt(final byte[] data, final int start) {
584         if (data.length < + start) {
585             throw new IllegalArgumentException(
586                 "Byte array to short: " + data.length
587             );
588         }
589 
590         return ((data[start]     << 24+
591                 (data[+ start<< 16+
592                 (data[+ start<< 8+
593                 (data[+ start]));
594     }
595 
596 }