001 package com.softnetConsult.utils.math;
002
003
004 /**
005 * This class provides implementations for various bit-level operations of Java types that can
006 * be used as bit-maps.
007 *
008 * <p style="font-size:smaller;">This product includes software developed by the
009 * <strong>SoftNet-Consult Java Utility Library</strong> project and its contributors.<br />
010 * (<a href="http://java-tools.sourceforge.net" target="_blank">http://java-tools.sourceforge.net</a>)<br />
011 * Copyright (c) 2007-2008 SoftNet-Consult.<br />
012 * Copyright (c) 2007-2008 G. Paperin.<br />
013 * All rights reserved.
014 * </p>
015 * <p style="font-size:smaller;">File: BitmapTools.java<br />
016 * Library API version: {@value com.softnetConsult.utils.APIProperties#apiVersion}<br />
017 * Java compliance version: {@value com.softnetConsult.utils.APIProperties#javaComplianceVersion}
018 * </p>
019 * <p style="font-size:smaller;">Redistribution and use in source and binary forms, with or
020 * without modification, are permitted provided that the following terms and conditions are met:
021 * </p>
022 * <p style="font-size:smaller;">1. Redistributions of source code must retain the above
023 * acknowledgement of the SoftNet-Consult Java Utility Library project, the above copyright
024 * notice, this list of conditions and the following disclaimer.<br />
025 * 2. Redistributions in binary form must reproduce the above acknowledgement of the
026 * SoftNet-Consult Java Utility Library project, the above copyright notice, this list of
027 * conditions and the following disclaimer in the documentation and/or other materials
028 * provided with the distribution.<br />
029 * 3. All advertising materials mentioning features or use of this software or any derived
030 * software must display the following acknowledgement:<br />
031 * <em>This product includes software developed by the SoftNet-Consult Java Utility Library
032 * project and its contributors.</em>
033 * </p>
034 * <p style="font-size:smaller;">THIS SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY
035 * OF ANY KIND, EXPRESSED OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
036 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
037 * THE AUTHORS, CONTRIBUTORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
038 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR
039 * IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
040 * </p>
041 * @author Greg Paperin (<a href="http://www.paperin.org" target="_blank">http://www.paperin.org</a>)
042 * @version {@value com.softnetConsult.utils.APIProperties#apiVersion}
043 */
044 public final class BitmapTools {
045
046 /**
047 * Prevents instances of this class from being created
048 * as this class contains only static utility methods.
049 */
050 private BitmapTools() {}
051
052 /**
053 * Computes the haming distance between the bit-patterns that represent {@code a}
054 * and {@code b}, only {@code len} rightmost bits are considered.
055 *
056 * @param a Some bit-pattern.
057 * @param b Some bit-pattern.
058 * @param len Number of rightmost bits to consider (0 to 32).
059 * @return The hamming distance between the two specified patterns.
060 */
061 public static int hammingDistance(final int a, final int b, final int len) {
062
063 int diff = a ^ b;
064
065 final int ignoreBits = 32 - len;
066 diff = (diff << ignoreBits) >>> ignoreBits;
067
068 int dist = 0;
069 while (0x00 != diff) {
070 if (0x00 != (diff & 0x00000001))
071 dist++;
072 diff >>>= 1;
073 }
074 return dist;
075 }
076
077
078 /**
079 * Computes the haming distance between the bit-patterns that represent {@code a}
080 * and {@code b}.
081 *
082 * @param a Some bit-pattern.
083 * @param b Some bit-pattern.
084 * @return The hamming distance between the two specified patterns.
085 */
086 public static int hammingDistance(final int a, final int b) {
087
088 int diff = a ^ b;
089 int dist = 0;
090 while (0x00 != diff) {
091 if (0x00 != (diff & 0x00000001))
092 dist++;
093 diff >>>= 1;
094 }
095 return dist;
096 }
097
098
099 /**
100 * Computes the haming distance between the bit-patterns that represent {@code a}
101 * and {@code b}, only {@code len} rightmost bits are considered.
102 *
103 * @param a Some bit-pattern.
104 * @param b Some bit-pattern.
105 * @param len Number of rightmost bits to consider (0 to 64).
106 * @return The hamming distance between the two specified patterns.
107 */
108 public static int hammingDistance(final long a, final long b, final int len) {
109
110 long diff = a ^ b;
111
112 final int ignoreBits = 64 - len;
113 diff = (diff << ignoreBits) >>> ignoreBits;
114
115 int dist = 0;
116 while (0x00L != diff) {
117 if (0x00L != (diff & 0x0000000000000001L))
118 dist++;
119 diff >>>= 1;
120 }
121 return dist;
122 }
123
124
125 /**
126 * Computes the haming distance between the bit-patterns that represent {@code a}
127 * and {@code b}.
128 *
129 * @param a Some bit-pattern.
130 * @param b Some bit-pattern.
131 * @return The hamming distance between the two specified patterns.
132 */
133 public static int hammingDistance(final long a, final long b) {
134
135 long diff = a ^ b;
136 int dist = 0;
137 while (0x00L != diff) {
138 if (0x00L != (diff & 0x0000000000000001L))
139 dist++;
140 diff >>>= 1;
141 }
142 return dist;
143 }
144
145
146 /**
147 * Computes the hamming distance between two boolean arrays of the same length.
148 *
149 * @param a A non-null array.
150 * @param b A non-null array.
151 * @return The number of positions in which the two specified arrays differ.
152 * @throws NullPointerException if a null reference was passed.
153 * @throws IllegalArgumentException if the specified arrays have different lengths.
154 */
155 public static int hammingDistance(final boolean[] a, final boolean[] b) {
156 if (null == a || null == b)
157 throw new NullPointerException("Cannot compute hamming distance using a null array");
158 if (a.length != b.length)
159 throw new IllegalArgumentException("Cannot compute hamming distance of two arrays of different lengths");
160 return hammingDistance(a, 0, b, 0, a.length);
161 }
162
163
164 /**
165 * Computes the hamming distance between specified sections of two boolean arrays.
166 *
167 * @param a A non-null array.
168 * @param offsA The position from which to start comparison in array {@code a} (from left).
169 * @param b A non-null array.
170 * @param offsB The position from which to start comparison in array {@code b} (from left).
171 * @param len The number of positions to compare.
172 * @return The number of positions in which the two specified arrays differ within the specified interval.
173 * @throws NullPointerException if a null reference was passed.
174 * @throws IllegalArgumentException if any of the specified intervals does not fit the corresponding array.
175 */
176 public static int hammingDistance(final boolean[] a, final int offsA, final boolean[] b, final int offsB,
177 final int len) {
178 if (null == a || null == b)
179 throw new NullPointerException("Cannot compute hamming distance using a null array");
180 if (offsA < 0 || a.length <= offsA || len < 0 || a.length <= offsA + len)
181 throw new IllegalArgumentException("Offset (" + offsA + ") and/or length (" + len +
182 ") not suitable for array A of length " + a.length);
183 if (offsB < 0 || b.length <= offsB || len < 0 || b.length <= offsB + len)
184 throw new IllegalArgumentException("Offset (" + offsB + ") and/or length (" + len +
185 ") not suitable for array B of length " + b.length);
186 int dist = 0;
187 for (int i = 0, pa = offsA, pb = offsB; i < len; i++, pa++, pb++) {
188 if (a[pa] != b[pb])
189 dist++;
190 }
191 return dist;
192 }
193
194
195 /**
196 * Sets a specified bit in the specified bit-map to 1.
197 *
198 * @param val A bit-map.
199 * @param bitNum The index of the bit to set (rightmost bit has index 0).
200 * @return The resulting bit-map.
201 */
202 public static byte setBit(final byte val, final int bitNum) {
203 return (byte) (val | (1 << bitNum));
204 }
205
206
207 /**
208 * Sets a specified bit in the specified bit-map to 1.
209 *
210 * @param val A bit-map.
211 * @param bitNum The index of the bit to set (rightmost bit has index 0).
212 * @return The resulting bit-map.
213 */
214 public static short setBit(final short val, final int bitNum) {
215 return (short) (val | (1 << bitNum));
216 }
217
218
219 /**
220 * Sets a specified bit in the specified bit-map to 1.
221 *
222 * @param val A bit-map.
223 * @param bitNum The index of the bit to set (rightmost bit has index 0).
224 * @return The resulting bit-map.
225 */
226 public static int setBit(final int val, final int bitNum) {
227 return val | (1 << bitNum);
228 }
229
230
231 /**
232 * Sets a specified bit in the specified bit-map to 1.
233 *
234 * @param val A bit-map.
235 * @param bitNum The index of the bit to set (rightmost bit has index 0).
236 * @return The resulting bit-map.
237 */
238 public static long setBit(final long val, final int bitNum) {
239 return val | (1L << bitNum);
240 }
241
242
243 /**
244 * Clears a specified bit in the specified bit-map to 0.
245 *
246 * @param val A bit-map.
247 * @param bitNum The index of the bit to clear (rightmost bit has index 0).
248 * @return The resulting bit-map.
249 */
250 public static byte clearBit(final byte val, final int bitNum) {
251 return (byte) (val & ~(1 << bitNum));
252 }
253
254
255 /**
256 * Clears a specified bit in the specified bit-map to 0.
257 *
258 * @param val A bit-map.
259 * @param bitNum The index of the bit to clear (rightmost bit has index 0).
260 * @return The resulting bit-map.
261 */
262 public static short clearBit(final short val, final int bitNum) {
263 return (short) (val & ~(1 << bitNum));
264 }
265
266
267 /**
268 * Clears a specified bit in the specified bit-map to 0.
269 *
270 * @param val A bit-map.
271 * @param bitNum The index of the bit to clear (rightmost bit has index 0).
272 * @return The resulting bit-map.
273 */
274 public static int clearBit(final int val, final int bitNum) {
275 return val & ~(1 << bitNum);
276 }
277
278
279 /**
280 * Clears a specified bit in the specified bit-map to 0.
281 *
282 * @param val A bit-map.
283 * @param bitNum The index of the bit to clear (rightmost bit has index 0).
284 * @return The resulting bit-map.
285 */
286 public static long clearBit(final long val, final int bitNum) {
287 return val & ~(1L << bitNum);
288 }
289
290
291 /**
292 * Toggles a specified bit in the specified bit-map
293 * from 1 to 0 or from 0 to 1 respectively.
294 *
295 * @param val A bit-map.
296 * @param bitNum The index of the bit to toggle (rightmost bit has index 0).
297 * @return The resulting bit-map.
298 */
299 public static byte toggleBit(final byte val, final int bitNum) {
300 return (byte) (val ^ (1 << bitNum));
301 }
302
303
304 /**
305 * Toggles a specified bit in the specified bit-map
306 * from 1 to 0 or from 0 to 1 respectively.
307 *
308 * @param val A bit-map.
309 * @param bitNum The index of the bit to toggle (rightmost bit has index 0).
310 * @return The resulting bit-map.
311 */
312 public static short toggleBit(final short val, final int bitNum) {
313 return (short) (val ^ (1 << bitNum));
314 }
315
316
317 /**
318 * Toggles a specified bit in the specified bit-map
319 * from 1 to 0 or from 0 to 1 respectively.
320 *
321 * @param val A bit-map.
322 * @param bitNum The index of the bit to toggle (rightmost bit has index 0).
323 * @return The resulting bit-map.
324 */
325 public static int toggleBit(final int val, final int bitNum) {
326 return val ^ (1 << bitNum);
327 }
328
329
330 /**
331 * Toggles a specified bit in the specified bit-map
332 * from 1 to 0 or from 0 to 1 respectively.
333 *
334 * @param val A bit-map.
335 * @param bitNum The index of the bit to toggle (rightmost bit has index 0).
336 * @return The resulting bit-map.
337 */
338 public static long toggleBit(final long val, final int bitNum) {
339 return val ^ (1L << bitNum);
340 }
341
342
343 /**
344 * Checks the state of a specified bit in the specified bit-map.
345 *
346 * @param val A bit-map.
347 * @param bitNum The index of the bit to toggle (rightmost bit has index 0).
348 * @return {@code true} if the specified bit is {@code 1};
349 * {@code false} if the specified bit is {@code 0}.
350 */
351 public static boolean checkBit(final byte val, final int bitNum) {
352 return 0 != (val & (1 << bitNum));
353 }
354
355
356 /**
357 * Checks the state of a specified bit in the specified bit-map.
358 *
359 * @param val A bit-map.
360 * @param bitNum The index of the bit to toggle (rightmost bit has index 0).
361 * @return {@code true} if the specified bit is {@code 1};
362 * {@code false} if the specified bit is {@code 0}.
363 */
364 public static boolean checkBit(final short val, final int bitNum) {
365 return 0 != (val & (1 << bitNum));
366 }
367
368
369 /**
370 * Checks the state of a specified bit in the specified bit-map.
371 *
372 * @param val A bit-map.
373 * @param bitNum The index of the bit to toggle (rightmost bit has index 0).
374 * @return {@code true} if the specified bit is {@code 1};
375 * {@code false} if the specified bit is {@code 0}.
376 */
377 public static boolean checkBit(final int val, final int bitNum) {
378 return 0 != (val & (1 << bitNum));
379 }
380
381
382 /**
383 * Checks the state of a specified bit in the specified bit-map.
384 *
385 * @param val A bit-map.
386 * @param bitNum The index of the bit to toggle (rightmost bit has index 0).
387 * @return {@code true} if the specified bit is {@code 1};
388 * {@code false} if the specified bit is {@code 0}.
389 */
390 public static boolean checkBit(final long val, final int bitNum) {
391 return 0L != (val & (1L << bitNum));
392 }
393
394 } // public class BitmapTools