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 * BitVector.java
019 *
020 * implements a bit vector
021 */
022 public final class BitVector implements Serializable {
023 /** Support for serialization */
024 static final long serialVersionUID = 6961578653974090041L;
025
026 private static final int LOG_BITS_PER_UNIT = 5;
027 private static final int MASK = 0xffffffff;
028 private static final int LOW_MASK = 0x1f;
029 private final int[] bits;
030 private final int nbits;
031
032 /**
033 * Convert bitIndex to a subscript into the bits[] array.
034 */
035 private static int subscript(int bitIndex) {
036 return bitIndex >> LOG_BITS_PER_UNIT;
037 }
038
039 /**
040 * Creates an empty string with the specified size.
041 * @param nbits the size of the string
042 */
043 public BitVector(int nbits) {
044 // subscript(nbits) is the length of the array needed to
045 // hold nbits
046 bits = new int[subscript(nbits) + 1];
047 this.nbits = nbits;
048 }
049
050 /**
051 * Creates a copy of a Bit String
052 * @param s the string to copy
053 */
054 public BitVector(BitVector s) {
055 bits = new int[s.bits.length];
056 this.nbits = s.nbits;
057 System.arraycopy(s.bits, 0, this.bits, 0, s.bits.length);
058 }
059
060 /**
061 * Sets all bits.
062 */
063 public void setAll() {
064 for (int i = 0; i < bits.length; i++) {
065 bits[i] = MASK;
066 }
067 }
068
069 /**
070 * Sets a bit.
071 * @param bit the bit to be set
072 */
073 public void set(int bit) {
074 int shiftBits = bit & LOW_MASK;
075 bits[subscript(bit)] |= (1 << shiftBits);
076 }
077
078 /**
079 * Clears all bits.
080 */
081 public void clearAll() {
082 for (int i = 0; i < bits.length; i++) {
083 bits[i] = 0;
084 }
085 }
086
087 /**
088 * Clears a bit.
089 * @param bit the bit to be cleared
090 */
091 public void clear(int bit) {
092 int shiftBits = bit & LOW_MASK;
093 bits[subscript(bit)] &= ~(1 << shiftBits);
094 }
095
096 /**
097 * Gets a bit.
098 * @param bit the bit to be gotten
099 */
100 public boolean get(int bit) {
101 int shiftBits = bit & LOW_MASK;
102 int n = subscript(bit);
103 return ((bits[n] & (1 << shiftBits)) != 0);
104 }
105
106 /**
107 * Logically NOT this bit string
108 */
109 public void not() {
110 for (int i = 0; i < bits.length; i++) {
111 bits[i] ^= MASK;
112 }
113 }
114
115 /**
116 * Return the NOT of a bit string
117 */
118 public static BitVector not(BitVector s) {
119 BitVector b = new BitVector(s);
120 b.not();
121 return b;
122 }
123
124 /**
125 * Logically ANDs this bit set with the specified set of bits.
126 * @param set the bit set to be ANDed with
127 */
128 public void and(BitVector set) {
129 if (this == set) {
130 return;
131 }
132 int n = bits.length;
133 for (int i = n; i-- > 0;) {
134 bits[i] &= set.bits[i];
135 }
136 }
137
138 /**
139 * Return a new bit string as the AND of two others.
140 */
141 public static BitVector and(BitVector b1, BitVector b2) {
142 BitVector b = new BitVector(b1);
143 b.and(b2);
144 return b;
145 }
146
147 /**
148 * Logically ORs this bit set with the specified set of bits.
149 * @param set the bit set to be ORed with
150 */
151 public void or(BitVector set) {
152 if (this == set) { // should help alias analysis
153 return;
154 }
155 int setLength = set.bits.length;
156 for (int i = setLength; i-- > 0;) {
157 bits[i] |= set.bits[i];
158 }
159 }
160
161 /**
162 * Return a new BitVector as the OR of two others
163 */
164 public static BitVector or(BitVector b1, BitVector b2) {
165 BitVector b = new BitVector(b1);
166 b.or(b2);
167 return b;
168 }
169
170 /**
171 * Logically XORs this bit set with the specified set of bits.
172 * @param set the bit set to be XORed with
173 */
174 public void xor(BitVector set) {
175 int setLength = set.bits.length;
176 for (int i = setLength; i-- > 0;) {
177 bits[i] ^= set.bits[i];
178 }
179 }
180
181 /**
182 * Check if the intersection of the two sets is empty
183 * @param other the set to check intersection with
184 */
185 public boolean intersectionEmpty(BitVector other) {
186 int n = bits.length;
187 for (int i = n; i-- > 0;) {
188 if ((bits[i] & other.bits[i]) != 0) return false;
189 }
190 return true;
191 }
192
193 /**
194 * Copies the values of the bits in the specified set into this set.
195 * @param set the bit set to copy the bits from
196 */
197 public void copyBits(BitVector set) {
198 System.arraycopy(set.bits, 0, this.bits, 0, set.bits.length);
199 }
200
201 /**
202 * Gets the hashcode.
203 */
204 public int hashCode() {
205 int h = 1234;
206 for (int i = bits.length; --i >= 0;) {
207 h ^= bits[i] * (i + 1);
208 }
209 return h;
210 }
211
212 /**
213 * How many bits are set?
214 */
215 public int populationCount() {
216 int count = 0;
217 for (int bit : bits) {
218 count += Integer.bitCount(bit);
219 }
220 return count;
221 }
222
223 /**
224 * Calculates and returns the set's size in bits.
225 * The maximum element in the set is the size - 1st element.
226 */
227 public int length() {
228 return bits.length << LOG_BITS_PER_UNIT;
229 }
230
231 /**
232 * Compares this object against the specified object.
233 * @param obj the object to compare with
234 * @return true if the objects are the same; false otherwise.
235 */
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 public String toString() {
270 StringBuilder buffer = new StringBuilder();
271 boolean needSeparator = false;
272 buffer.append('{');
273 // int limit = length();
274 int limit = this.nbits;
275 for (int i = 0; i < limit; i++) {
276 if (get(i)) {
277 if (needSeparator) {
278 buffer.append(", ");
279 } else {
280 needSeparator = true;
281 }
282 buffer.append(i);
283 }
284 }
285 buffer.append('}');
286 return buffer.toString();
287 }
288 }