1 /*
2 * Copyright (C) 2012-2015 Christian Sterzl <christian.sterzl@gmail.com>
3 *
4 * This file is part of Bittwiddling.
5 *
6 * Bittwiddling is free software: you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation, either version 3 of the License, or
9 * (at your option) any later version.
10 *
11 * Bittwiddling is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
15 *
16 * You should have received a copy of the GNU General Public License
17 * along with Bittwiddling. If not, see <http://www.gnu.org/licenses/>.
18 */
19
20 package com.vcollaborate.bitwise;
21
22 import com.vcollaborate.math.CombinatoricUtils;
23
24 import java.util.BitSet;
25
26 public final class BinaryUtils {
27
28 private BinaryUtils() {
29 }
30
31 /**
32 * Converts {@code value} into a {@link BitSet} of size {@code size}.
33 */
34 public static final BitSet toBitSet(final int size, final long value) {
35 BitSet bits = new BitSet(size);
36 int idx = 0;
37 long tmp = value;
38 while (tmp != 0L) {
39 if (tmp % 2L != 0L) {
40 bits.set(idx);
41 }
42 ++idx;
43 tmp = tmp >>> 1;
44 }
45 return bits;
46 }
47
48 /**
49 * Converts the {@link BitSet} {@code bits} into a long value.
50 * <p>
51 * This is the reverse operation from {@link #toBitSet(int, long)}.
52 */
53 public static final long fromBitSet(final BitSet bits) {
54 long value = 0L;
55 for (int i = 0; i < bits.size(); i++) {
56 value += bits.get(i) ? (1L << i) : 0L;
57 }
58 return value;
59 }
60
61 /**
62 * Compute the lexicographically next bit permutation.
63 *
64 * Suppose we have a pattern of N bits set to 1 in an integer and we want the next permutation of
65 * N 1 bits in a lexicographical sense. For example, if N is 3 and the bit pattern is 00010011,
66 * the next patterns would be 00010101, 00010110, 00011001,00011010, 00011100, 00100011, and so
67 * forth.
68 */
69 public static final long nextPermutation(long val) {
70 long tmp = val | (val - 1);
71 return (tmp + 1) | (((-tmp & -~tmp) - 1) >> (Long.numberOfTrailingZeros(val) + 1));
72 }
73
74 /**
75 * Returns an array containing all permutations of a defined bitset with {@code bits} set and
76 * maximum length of {@code length}.
77 */
78 public static final long[] getAllPermutations(int bits, int length) {
79 long min = allOnes(bits);
80 long permutations = CombinatoricUtils.combinations(length, bits);
81 long[] retVal = new long[(int) permutations];
82
83 long val = min;
84 for (int idx = 0; idx < permutations; idx++) {
85 retVal[idx] = val;
86 val = nextPermutation(val);
87 }
88 return retVal;
89 }
90
91 /**
92 * Calculates the hamming distance between the two given values.
93 */
94 public static final int getHammingDistance(final long val1, final long val2) {
95 return Long.bitCount(val1 ^ val2);
96 }
97
98 /**
99 * Returns a value with all bits set to 1 of length {@code length}.
100 */
101 public static final long allOnes(final long length) {
102 return (1 << length) - 1;
103 }
104
105 /**
106 * Determines if the bit at position {@code pos} in the value {@code val} is set.
107 */
108 public static final boolean isBitSet(final long val, final int pos) {
109 return (val & (1 << pos)) != 0;
110 }
111
112 /**
113 * Returns the number of bits set.
114 */
115 public static final int[] getBitsSet(final long val) {
116 long tmp = val;
117 int[] retVal = new int[Long.bitCount(val)];
118 for (int i = 0; i < retVal.length; i++) {
119 retVal[i] = Long.numberOfTrailingZeros(tmp);
120 tmp = tmp ^ Long.lowestOneBit(tmp);
121 }
122 return retVal;
123 }
124 }