bit.java
001 /*
002  * Java Genetic Algorithm Library (jenetics-1.5.0).
003  * Copyright (c) 2007-2013 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: 2013-12-05 $</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     public static byte[] toByteArray(final LargeInteger value) {
358         final int bytes = (value.bitLength() >>> 31;
359 
360         final byte[] array = new byte[bytes];
361         value.toByteArray(array, 0);
362         return reverse(array);
363     }
364 
365     /**
366      * Convert the given byte array into an {@link LargeInteger}.
367      *
368      @see #toByteArray(LargeInteger)
369      *
370      @param array the byte array to convert.
371      @return the {@link LargeInteger} built from the given byte array.
372      */
373     public static LargeInteger toLargeInteger(final byte[] array) {
374         return LargeInteger.valueOf(reverse(array.clone())0, array.length);
375     }
376 
377 
378     static byte[] reverse(final byte[] array) {
379         int i = 0;
380         int j = array.length;
381 
382         while (i < j) {
383             swap(array, i++, --j);
384         }
385 
386         return array;
387     }
388 
389     private static void swap(final byte[] array, final int i, final int j) {
390         final byte temp = array[i];
391         array[i= array[j];
392         array[j= temp;
393     }
394 
395     /**
396      * Convert a binary representation of the given byte array to a string. The
397      * string has the following format:
398      <pre>
399      *  Byte:       3        2        1        0
400      *              |        |        |        |
401      *  Array: "11110011|10011101|01000000|00101010"
402      *          |                 |        |      |
403      *  Bit:    23                15       7      0
404      </pre>
405      <i>Only the array string is printed.</i>
406      *
407      @see #fromByteString(String)
408      *
409      @param data the byte array to convert to a string.
410      @return the binary representation of the given byte array.
411      */
412     public static String toByteString(final byte... data) {
413         final StringBuilder out = new StringBuilder();
414 
415         if (data.length > 0) {
416             for (int j = 7; j >= 0; --j) {
417                 out.append((data[data.length - 1>>> j1);
418             }
419         }
420         for (int i = data.length - 2; i >= ;--i) {
421             out.append('|');
422             for (int j = 7; j >= 0; --j) {
423                 out.append((data[i>>> j1);
424             }
425         }
426 
427         return out.toString();
428     }
429 
430     /**
431      * Convert a string which was created with the {@link #toByteString(byte...)}
432      * method back to an byte array.
433      *
434      @see #toByteString(byte...)
435      *
436      @param data the string to convert.
437      @return the byte array.
438      @throws IllegalArgumentException if the given data string could not be
439      *          converted.
440      */
441      public static byte[] fromByteString(final String data) {
442         final String[] parts = data.split("\\|");
443         final byte[] bytes = new byte[parts.length];
444 
445         for (int i = 0; i < parts.length; ++i) {
446             if (parts[i].length() != 8) {
447                 throw new IllegalArgumentException(
448                     "Byte value doesn't contain 8 bit: " + parts[i]
449                 );
450             }
451 
452             try {
453                 bytes[parts.length - - i(byte)Integer.parseInt(parts[i]2);
454             catch (NumberFormatException e) {
455                 throw new IllegalArgumentException(e);
456             }
457         }
458 
459         return bytes;
460     }
461 
462     /**
463      * Create a new {@code byte[]} array which can store at least the number
464      * of bits as defined by the given {@code length} parameter.
465      *
466      @param length the number of bits, the returned byte array can store.
467      @return the new byte array.s
468      *
469      @deprecated Use {@link #newArray(int)} instead.
470      */
471     @Deprecated
472     public static byte[] newBitArray(final int length) {
473         return newArray(length);
474     }
475 
476     /**
477      * Create a new {@code byte[]} array which can store at least the number
478      * of bits as defined by the given {@code length} parameter.
479      *
480      @param length the number of bits, the returned byte array can store.
481      @return the new byte array.s
482      */
483     public static byte[] newArray(final int length) {
484         return new byte[toByteLength(length)];
485     }
486 
487     /**
488      * Create a new {@code byte[]} array which can store at least the number
489      * of bits as defined by the given {@code length} parameter. The returned
490      * byte array is initialized with ones according to the given ones
491      * probability {@code p}.
492      *
493      @param length the number of bits, the returned byte array can store.
494      @param p the ones probability of the returned byte array.
495      @return the new byte array.s
496      @throws IllegalArgumentException if {@code p} is not a valid probability.
497      *
498      @deprecated Use {@link #newArray(int, double)} instead.
499      */
500     @Deprecated
501     public static byte[] newBitArray(final int length, final double p) {
502         return newArray(length, p);
503     }
504 
505     /**
506      * Create a new {@code byte[]} array which can store at least the number
507      * of bits as defined by the given {@code length} parameter. The returned
508      * byte array is initialized with ones according to the given ones
509      * probability {@code p}.
510      *
511      @param length the number of bits, the returned byte array can store.
512      @param p the ones probability of the returned byte array.
513      @return the new byte array.s
514      @throws IllegalArgumentException if {@code p} is not a valid probability.
515      */
516     public static byte[] newArray(final int length, final double p) {
517         final byte[] bytes = newArray(length);
518 
519         final IndexStream stream = IndexStream.Random(length, p);
520         for (int i = stream.next(); i != -1; i = stream.next()) {
521             bytes[i >>> 3|= << (i & 7);
522         }
523 
524         return bytes;
525     }
526 
527     /**
528      * Return the minimum number of bytes to store the given number of bits.
529      *
530      @param bitLength the number of bits
531      @return the number of bytes needed to store the given number of bits.
532      */
533     public static int toByteLength(final int bitLength) {
534         return (bitLength & 7== (bitLength >>> 3(bitLength >>> 31;
535     }
536 
537     static long toLong(final byte[] data) {
538         return
539             (((long)data[0<< 56+
540             ((long)(data[1255<< 48+
541             ((long)(data[2255<< 40+
542             ((long)(data[3255<< 32+
543             ((long)(data[4255<< 24+
544             ((data[5255<< 16+
545             ((data[6255<<  8+
546             ((data[7255)));
547     }
548 
549     static byte[] toBytes(final long value) {
550         final byte[] bytes = new byte[8];
551         bytes[0(byte)(value >>> 56);
552         bytes[1(byte)(value >>> 48);
553         bytes[2(byte)(value >>> 40);
554         bytes[3(byte)(value >>> 32);
555         bytes[4(byte)(value >>> 24);
556         bytes[5(byte)(value >>> 16);
557         bytes[6(byte)(value >>>  8);
558         bytes[7(byte)(value);
559         return bytes;
560     }
561 
562     static byte[] writeInt(final int v, final byte[] data, final int start) {
563         if (data.length < + start) {
564             throw new IllegalArgumentException(
565                 "Byte array to short: " + data.length
566             );
567         }
568 
569         data[start]     (byte)((v >>> 240xFF);
570         data[+ start(byte)((v >>> 160xFF);
571         data[+ start(byte)((v >>>  80xFF);
572         data[+ start(byte)((v)        0xFF);
573 
574         return data;
575     }
576 
577     static int readInt(final byte[] data, final int start) {
578         if (data.length < + start) {
579             throw new IllegalArgumentException(
580                 "Byte array to short: " + data.length
581             );
582         }
583 
584         return ((data[start]     << 24+
585                 (data[+ start<< 16+
586                 (data[+ start<< 8+
587                 (data[+ start]));
588     }
589 
590 }
591 
592 
593