Bit mapping in java

Java/Collections Data Structure/BitSet

Implementation of a bit map of any size, together with static methods to manipulate int, byte and byte[] values as bit maps

/* Copyright (c) 2001-2009, The HSQL Development Group

* All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions are met: * * Redistributions of source code must retain the above copyright notice, this * list of conditions and the following disclaimer. * * Redistributions in binary form must reproduce the above copyright notice, * this list of conditions and the following disclaimer in the documentation * and/or other materials provided with the distribution. * * Neither the name of the HSQL Development Group nor the names of its * contributors may be used to endorse or promote products derived from this * software without specific prior written permission. * * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE * ARE DISCLAIMED. IN NO EVENT SHALL HSQL DEVELOPMENT GROUP, HSQLDB.ORG, * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */

* Implementation of a bit map of any size, together with static methods to * manipulate int, byte and byte[] values as bit maps. * * @author Fred Toussi (fredt@users dot sourceforge.net) * @version 1.9.0 * @since 1.8.0

int defaultCapacity; int capacity; int[] map; int limitPos; public BitMap(int initialCapacity) < int words = initialCapacity / 32; if (initialCapacity % 32 != 0) < words++; >defaultCapacity = capacity = words * 32; map = new int[words]; limitPos = 0; > public int size() < return limitPos; >public void setSize(int size) < limitPos = size; >/** * Resets to blank with original capacity */ public void reset() < map = new int[defaultCapacity / 32]; capacity = defaultCapacity; limitPos = 0; >/** * Sets pos and returns old value */ public int set(int pos) < while (pos >= capacity) < doubleCapacity(); >if (pos >= limitPos) < limitPos = pos + 1; >int windex = pos >> 5; int mask = 0x80000000 >>> (pos & 0x1F); int word = map[windex]; int result = (word & mask) == 0 ? 0 : 1; map[windex] = (word | mask); return result; > /** * Unsets pos and returns old value */ public int unset(int pos) < while (pos >= capacity) < doubleCapacity(); >if (pos >= limitPos) < limitPos = pos + 1; return 0; >int windex = pos >> 5; int mask = 0x80000000 >>> (pos & 0x1F); int word = map[windex]; int result = (word & mask) == 0 ? 0 : 1; mask = ~mask; map[windex] = (word & mask); return result; > public int get(int pos) < while (pos >= capacity) < doubleCapacity(); >if (pos >= limitPos) < limitPos = pos + 1; return 0; >int windex = pos >> 5; int mask = 0x80000000 >>> (pos & 0x1F); int word = map[windex]; return (word & mask) == 0 ? 0 : 1; > public boolean isSet(int pos) < return get(pos) == 1; >public byte[] getBytes() < byte[] buf = new byte[(limitPos + 7) / 8]; if (buf.length == 0) < return buf; >for (int i = 0; ; ) < int v = map[i / 4]; buf[i++] = (byte) (v >>> 24); if (i == buf.length) < break; >buf[i++] = (byte) (v >>> 16); if (i == buf.length) < break; >buf[i++] = (byte) (v >>> 8); if (i == buf.length) < break; >buf[i++] = (byte) v; if (i == buf.length) < break; >> return buf; > private void doubleCapacity() < int[] newmap = new int[map.length * 2]; capacity *= 2; System.arraycopy(map, 0, newmap, 0, map.length); map = newmap; >/** * copy the byte value into the map at given position (0, 24) */ public static int setByte(int map, byte value, int pos) < int intValue = (value & 0xff) >> pos; mask = ~mask; map &= mask; return (map | intValue); > public static int set(int map, int pos) < int mask = 0x80000000 >>> pos; return (map | mask); > public static byte set(byte map, int pos) < int mask = 0x00000080 >>> pos; return (byte) (map | mask); > public static int unset(int map, int pos) < int mask = 0x80000000 >>> pos; mask = ~mask; return (map & mask); > public static boolean isSet(int map, int pos) < int mask = 0x80000000 >>> pos; return (map & mask) == 0 ? false : true; > public static boolean isSet(byte map, int pos) < int mask = 0x00000080 >>> pos; return (map & mask) == 0 ? false : true; > public static boolean isSet(byte[] map, int pos) < int mask = 0x00000080 >>> (pos & 0x07);; int index = pos / 8; if (index >= map.length) < return false; >byte b = map[index]; return (b & mask) == 0 ? false : true; > public static void unset(byte[] map, int pos) < int mask = 0x00000080 >>> (pos & 0x07); mask = ~mask; int index = pos / 8; if (index >= map.length) < return; >byte b = map[index]; map[index] = (byte) (b & mask); > public static void set(byte[] map, int pos) < int mask = 0x00000080 >>> (pos & 0x07); int index = pos / 8; if (index >= map.length) < return; >byte b = map[index]; map[index] = (byte) (b | mask); > /** * AND count bits from source with map contents starting at pos */ public static void and(byte[] map, int pos, byte source, int count) < int shift = pos & 0x07; int mask = (source & 0xff) >>> shift; int innermask = 0xff >> shift; int index = pos / 8; if (count < 8) < innermask = innermask >>> (8 - count); innermask = innermask mask &= innermask; innermask = ~innermask; if (index >= map.length) < return; >byte b = map[index]; map[index] = (byte) (b & innermask); b = (byte) (b & mask); map[index] = (byte) (map[index] | b); if (shift == 0) < return; >shift = 8 - shift; if (count > shift) < mask = ((source & 0xff) >> shift; innermask = 0xff00 >>> shift; innermask = ~innermask; b = map[index + 1]; map[index + 1] = (byte) (b & innermask); b = (byte) (b & mask); map[index + 1] = (byte) (map[index + 1] | b); > > /** * OR count bits from source with map contents starting at pos */ public static void or(byte[] map, int pos, byte source, int count) < int shift = pos & 0x07; int mask = (source & 0xff) >>> shift; int index = pos / 8; if (index >= map.length) < return; >byte b = (byte) (map[index] | mask); map[index] = b; if (shift == 0) < return; >shift = 8 - shift; if (count > shift) < mask = ((source & 0xff) >> shift; b = (byte) (map[index + 1] | mask); map[index + 1] = b; > > /** * overlay count bits from source on map contents starting at pos */ public static void overlay(byte[] map, int pos, byte source, int count) < int shift = pos & 0x07; int mask = (source & 0xff) >>> shift; int innermask = 0xff >> shift; int index = pos / 8; if (count < 8) < innermask = innermask >>> (8 - count); innermask = innermask mask &= innermask; innermask = ~innermask; if (index >= map.length) < return; >byte b = map[index]; b = (byte) (b & innermask); map[index] = (byte) (b | mask); if (shift == 0) < return; >shift = 8 - shift; if (count > shift) < mask = ((source & 0xff) >> shift; innermask = 0xff00 >>> shift; innermask = ~innermask; b = map[index + 1]; b = (byte) (b & innermask); map[index + 1] = (byte) (b | mask); > > public static int compare(byte[] a, byte[] b) < int shortLength = a.length >b.length ? b.length : a.length; for (int i = 0; i < shortLength; i++) < if (a[i] == b[i]) < continue; >return (((int) a[i]) & 0xff) > (((int) b[i]) & 0xff) ? 1 : -1; > if (a.length == b.length) < return 0; >return a.length > b.length ? 1 : -1; > public static byte[] and(byte[] a, byte[] b) < int length = a.length >b.length ? a.length : b.length; int shortLength = a.length > b.length ? b.length : a.length; byte[] map = new byte[length]; for (int i = 0; i < shortLength; i++) < map[i] = (byte) (a[i] & b[i]); >return map; > public static byte[] or(byte[] a, byte[] b) < int length = a.length >b.length ? a.length : b.length; int shortLength = a.length > b.length ? b.length : a.length; byte[] map = new byte[length]; if (length != shortLength) < byte[] source = a.length >b.length ? a : b; System.arraycopy(source, shortLength, map, shortLength, length - shortLength); > for (int i = 0; i < shortLength; i++) < map[i] = (byte) (a[i] | b[i]); >return map; > public static byte[] xor(byte[] a, byte[] b) < int length = a.length >b.length ? a.length : b.length; int shortLength = a.length > b.length ? b.length : a.length; byte[] map = new byte[length]; if (length != shortLength) < byte[] source = a.length >b.length ? a : b; System.arraycopy(source, shortLength, map, shortLength, length - shortLength); > for (int i = 0; i < shortLength; i++) < map[i] = (byte) (a[i] ^ b[i]); >return map; > public static byte[] not(byte[] a) < byte[] map = new byte[a.length]; for (int i = 0; i < a.length; i++) < map[i] = (byte) ~a[i]; >return map; > public static boolean hasAnyBitSet(byte[] map) < for (int i = 0; i < map.length; i++) < if (map[i] != 0) < return true; >> return false; > public static byte[] leftShift(byte[] map, int shiftBits) < byte[] newMap = new byte[map.length]; int shiftBytes = shiftBits / 8; if (shiftBytes >= map.length) < return newMap; >shiftBits = shiftBits % 8; if (shiftBits == 0) < for (int i = 0, j = shiftBytes; j < map.length; i++, j++) < newMap[i] = map[j]; >> else < for (int i = 0, j = shiftBytes; j < map.length; i++, j++) < int shifted = (map[j] & 0xff) 0) < newMap[i - 1] |= (byte) (shifted >>> 8); > > > return newMap; >

Источник

Build a Presence Map using bits of bytes in java

I have a requirement in Java where I need to build codec for Bit Map for n number of bytes. Each bit of byte will indicate presence of a field. We already know the position of each field i.e. which bit position will represent which field. Example:

bit position: field 0:TYPE 1:SIDE 2:QUANTITY 3:PRICE . . . 25:TIF

String value = "TYPE,SIDE,TIF"; 

I need to encode the presence of this field in byte and add it in bytebuffer and then I need to get bytes from this bytebuffer and decode it and I should get only these fields. The total bytes used will vary, might be 4, 6, 8. Can someone provide me solution for this.

The code is properly encoding and i can see the binary output of bytes: 01001011 00000011 00000100 00000000 00000000 But i m sure this code can drastically improved and there I need help

1 Answer 1

Use an enum form the bit positions. The ordinal() gives the index, the getName() the string presentation, and the static valueOf(String) the parsing from String to enum.

When using a BitSet with the enum:

BitSet fieldPresences = new BitSet(Field.COUNT); fieldPresences.set(Field.QUANTITY.ordinal(), true); Field field = Field.valueOf("QUANTITY"); 

However you can better use EnumSet which is as efficient too:

Set presentFields = EnumSet.of(Field.TYPE, Field.PRICE); 

Alternative to code given later in the question:

The code is fine enough. I have used PresenceMapCodec which can be given any enum class.

PresenceMapCodec codec = new PresenceMapCodec(Fields.class); String userInput = "ClientOrderID,SubmittingBrokerID,SecurityIDSource," + "TransactionTime,OriginalClientOrderID,OrderID,OrderCapacity"; Set fieldset = codec.encode(userInput); String decodedValue = codec.decode(fieldset); public enum Fields < ClientOrderID, SubmittingBrokerID, SecurityID, SecurityIDSource, SecurityExchange, BrokerLocationID, TransactionTime, Side, OriginalClientOrderID, OrderID, OwningBrokerID, OrderType, Price, OrderQuantity, TIF, PositionEffect, OrderRestrictions, MaxPriceLevels, OrderCapacity, Text, ExecutionID >public class PresenceMapCodec> < private final ClassenumClass; public PresenceMapCodec(Class enumClass) < this.enumClass = enumClass; >public String decode(Set fieldset) < StringBuilder sb = new StringBuilder(); for (E field : fieldset) < sb.append(field.name()).append(','); >if (sb.length() != 0) < sb.setLength(sb.length() - 1); // Remove trailing comma. >return sb.toString(); > public Set encode(String value_) < Setresults = EnumSet.noneOf(enumClass); StringTokenizer st = new StringTokenizer(value_, ","); while (st.hasMoreTokens()) < String token = st.nextToken().trim(); E field = E.valueOf(enumClass, token); // valueOf can throw IllegalArgumentException. results.add(field); >return results; > public String decode(ByteBuffer byteBuffer_) < E[] constants = enumClass.getEnumConstants(); int byteCount = (constants.length + 7) / 8; byte[] bytes = new byte[byteCount]; byteBuffer_.get(bytes); StringBuilder sb = new StringBuilder(); for (int i = 0; i < constants.length; ++i) < int b = bytes[i / 8]; int mask = 1 sb.append(constants[i].name()); > > return sb.toString(); > public void encode(String value_, ByteBuffer byteBuffer_) < Setfieldset = encode(value_); E[] constants = enumClass.getEnumConstants(); int byteCount = (constants.length + 7) / 8; byte[] bytes = new byte[byteCount]; for (E field : fieldset) < int i = field.ordinal(); bytes[i / 8] |= 1 byteBuffer_.put(bytes); > > 

Below the hood the same bit fiddling happens, though a bit more layered.

If you have wrong input something like the following happens:

Exception in thread "main" java.lang.IllegalArgumentException: No enum constant presensemap_v2.Fields.xxSubmittingBrokerID at java.lang.Enum.valueOf(Enum.java:238) at presensemap_v2.PresenceMapCodec.encode(PresenceMapCodec.java:33) at presensemap_v2.PresenceMapDemo.main(PresenceMapDemo.java:14) 

Источник