001 /*
002 * This file is part of the Jikes RVM project (http://jikesrvm.org).
003 *
004 * This file is licensed to You under the Eclipse Public License (EPL);
005 * You may not use this file except in compliance with the License. You
006 * may obtain a copy of the License at
007 *
008 * http://www.opensource.org/licenses/eclipse-1.0.php
009 *
010 * See the COPYRIGHT.txt file distributed with this work for information
011 * regarding copyright ownership.
012 */
013 package org.jikesrvm.util;
014
015 import java.io.Serializable;
016
017 /**
018 * Implements a bit vector.
019 */
020 public final class BitVector implements Serializable {
021 /** Support for serialization */
022 static final long serialVersionUID = 6961578653974090041L;
023
024 private static final int LOG_BITS_PER_UNIT = 5;
025 private static final int MASK = 0xffffffff;
026 private static final int LOW_MASK = 0x1f;
027 private final int[] bits;
028 private final int nbits;
029
030 /**
031 * Convert bitIndex to a subscript into the bits[] array.
032 */
033 private static int subscript(int bitIndex) {
034 return bitIndex >> LOG_BITS_PER_UNIT;
035 }
036
037 /**
038 * Creates an empty string with the specified size.
039 * @param nbits the size of the string
040 */
041 public BitVector(int nbits) {
042 // subscript(nbits) is the length of the array needed to
043 // hold nbits
044 bits = new int[subscript(nbits) + 1];
045 this.nbits = nbits;
046 }
047
048 /**
049 * Creates a copy of a Bit String
050 * @param s the string to copy
051 */
052 public BitVector(BitVector s) {
053 bits = new int[s.bits.length];
054 this.nbits = s.nbits;
055 System.arraycopy(s.bits, 0, this.bits, 0, s.bits.length);
056 }
057
058 /**
059 * Sets all bits.
060 */
061 public void setAll() {
062 for (int i = 0; i < bits.length; i++) {
063 bits[i] = MASK;
064 }
065 }
066
067 /**
068 * Sets a bit.
069 * @param bit the bit to be set
070 */
071 public void set(int bit) {
072 int shiftBits = bit & LOW_MASK;
073 bits[subscript(bit)] |= (1 << shiftBits);
074 }
075
076 /**
077 * Clears all bits.
078 */
079 public void clearAll() {
080 for (int i = 0; i < bits.length; i++) {
081 bits[i] = 0;
082 }
083 }
084
085 /**
086 * Clears a bit.
087 * @param bit the bit to be cleared
088 */
089 public void clear(int bit) {
090 int shiftBits = bit & LOW_MASK;
091 bits[subscript(bit)] &= ~(1 << shiftBits);
092 }
093
094 /**
095 * Gets a bit.
096 * @param bit the bit to be gotten
097 */
098 public boolean get(int bit) {
099 int shiftBits = bit & LOW_MASK;
100 int n = subscript(bit);
101 return ((bits[n] & (1 << shiftBits)) != 0);
102 }
103
104 /**
105 * Logically NOT this bit string
106 */
107 public void not() {
108 for (int i = 0; i < bits.length; i++) {
109 bits[i] ^= MASK;
110 }
111 }
112
113 /**
114 * Return the NOT of a bit string
115 */
116 public static BitVector not(BitVector s) {
117 BitVector b = new BitVector(s);
118 b.not();
119 return b;
120 }
121
122 /**
123 * Logically ANDs this bit set with the specified set of bits.
124 * @param set the bit set to be ANDed with
125 */
126 public void and(BitVector set) {
127 if (this == set) {
128 return;
129 }
130 int n = bits.length;
131 for (int i = n; i-- > 0;) {
132 bits[i] &= set.bits[i];
133 }
134 }
135
136 /**
137 * Return a new bit string as the AND of two others.
138 */
139 public static BitVector and(BitVector b1, BitVector b2) {
140 BitVector b = new BitVector(b1);
141 b.and(b2);
142 return b;
143 }
144
145 /**
146 * Logically ORs this bit set with the specified set of bits.
147 * @param set the bit set to be ORed with
148 */
149 public void or(BitVector set) {
150 if (this == set) { // should help alias analysis
151 return;
152 }
153 int setLength = set.bits.length;
154 for (int i = setLength; i-- > 0;) {
155 bits[i] |= set.bits[i];
156 }
157 }
158
159 /**
160 * Return a new BitVector as the OR of two others
161 */
162 public static BitVector or(BitVector b1, BitVector b2) {
163 BitVector b = new BitVector(b1);
164 b.or(b2);
165 return b;
166 }
167
168 /**
169 * Logically XORs this bit set with the specified set of bits.
170 * @param set the bit set to be XORed with
171 */
172 public void xor(BitVector set) {
173 int setLength = set.bits.length;
174 for (int i = setLength; i-- > 0;) {
175 bits[i] ^= set.bits[i];
176 }
177 }
178
179 /**
180 * Check if the intersection of the two sets is empty
181 * @param other the set to check intersection with
182 */
183 public boolean intersectionEmpty(BitVector other) {
184 int n = bits.length;
185 for (int i = n; i-- > 0;) {
186 if ((bits[i] & other.bits[i]) != 0) return false;
187 }
188 return true;
189 }
190
191 /**
192 * Copies the values of the bits in the specified set into this set.
193 * @param set the bit set to copy the bits from
194 */
195 public void copyBits(BitVector set) {
196 System.arraycopy(set.bits, 0, this.bits, 0, set.bits.length);
197 }
198
199 /**
200 * Gets the hashcode.
201 */
202 @Override
203 public int hashCode() {
204 int h = 1234;
205 for (int i = bits.length; --i >= 0;) {
206 h ^= bits[i] * (i + 1);
207 }
208 return h;
209 }
210
211 /**
212 * How many bits are set?
213 */
214 public int populationCount() {
215 int count = 0;
216 for (int bit : bits) {
217 count += Integer.bitCount(bit);
218 }
219 return count;
220 }
221
222 /**
223 * Calculates and returns the set's size in bits.
224 * The maximum element in the set is the size - 1st element.
225 */
226 public int length() {
227 return bits.length << LOG_BITS_PER_UNIT;
228 }
229
230 /**
231 * Compares this object against the specified object.
232 * @param obj the object to compare with
233 * @return true if the objects are the same; false otherwise.
234 */
235 @Override
236 public boolean equals(Object obj) {
237 if ((obj != null) && (obj instanceof BitVector)) {
238 if (this == obj) { // should help alias analysis
239 return true;
240 }
241 BitVector set = (BitVector) obj;
242 int n = bits.length;
243 if (n != set.bits.length) return false;
244 for (int i = n; i-- > 0;) {
245 if (bits[i] != set.bits[i]) {
246 return false;
247 }
248 }
249 return true;
250 }
251 return false;
252 }
253
254 public boolean isZero() {
255 int setLength = bits.length;
256 for (int i = setLength; i-- > 0;) {
257 if (bits[i] != 0) return false;
258 }
259 return true;
260 }
261
262 public BitVector dup() {
263 return new BitVector(this);
264 }
265
266 /**
267 * Converts the BitVector to a String.
268 */
269 @Override
270 public String toString() {
271 StringBuilder buffer = new StringBuilder();
272 boolean needSeparator = false;
273 buffer.append('{');
274 // int limit = length();
275 int limit = this.nbits;
276 for (int i = 0; i < limit; i++) {
277 if (get(i)) {
278 if (needSeparator) {
279 buffer.append(", ");
280 } else {
281 needSeparator = true;
282 }
283 buffer.append(i);
284 }
285 }
286 buffer.append('}');
287 return buffer.toString();
288 }
289 }