• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 482
  • Last Modified:

variable length bit array

what would be the best way to implement an array of bits in variable length (sometimes larger than 64 bits). I need to be able to get the bits between a given index to a given index in the minimal time.
If I use array of int or long then extracting a set of bits which are partly in one int and partly in another requires more advanced operation.
The data strucure used must be extremely efficient in space consumption as well as the time complexity of the extraction of bits from index to index.
0
doggz
Asked:
doggz
  • 10
  • 5
  • 2
  • +2
1 Solution
 
nir2002Commented:
Hi,

try use: java.math.BigInteger

Best regards
Nir
0
 
Igor BazarnyCommented:
Hi,

I couldn't imagine anithing better than array of ints or longs. I would probably use int to reserve long for calculations. Something like:

package ee.system;

public class BitArray{
     BitArray(int[] buffer, int usedbits){
         content = new int[buffer.length+1];
         System.arraycopy(buffer,0,content,0,buffer.length);
         used = usedbits;
     }
    int getBits(int start, int end){
        int size = end - start;
        if( size < 0 || size >32 ){
            throw new IllegalArgumentException("incorrect size");
        }
        if( end > used ){
            throw new IndexOutOfBoundsException(end+" > "+used);
        }
        if( start < 0 ){
            throw new IndexOutOfBoundsException(start+" < 0");
        }
        int index0 = start >> 5;
        long buffer = ((long)content[index0] << 32) | (0xFFFFFFFFl & content[index0+1]);
        int dropAtStart = start ^ (index0 << 5);
        return (int)( (buffer << dropAtStart) >>> (64-size));
    }

    public static void main(String[] args){
        int[] buffer = new int[]{0xCAFEBABE,0xDEADBEEF,0x12345678,0xFEDCBA98};
        for(int i=0; i<buffer.length; ++i){
            System.out.print(binStr(buffer[i]));
        }
        System.out.println();
        BitArray arr = new BitArray(buffer,128);
        for(int i=0; i<=96; ++i){
            System.out.println(binStr(arr.getBits(i,i+32)));
        }
    }
    private static String binStr(int val){
        String tail = Integer.toBinaryString(val);
        if( tail.length() == 32 ){
            return tail;
        }
        StringBuffer head = new StringBuffer(32);
        for(int i = tail.length(); i<32; ++i){
            head.append("0");
        }
        return head.append(tail).toString();
    }
    private int[] content;
    private int used;
}

Regards,
Igor Bazarny,
BrainBench MVP for Java 1
0
 
objectsCommented:
Have a look at java.util.BitSet class.
 
0
Never miss a deadline with monday.com

The revolutionary project management tool is here!   Plan visually with a single glance and make sure your projects get done.

 
yasser_helmyCommented:
why not use an array of boolean with true meaning 1 and false meaning 0.
0
 
doggzAuthor Commented:
I don't think boolean array will be saved in less than byte[length of boolean array]
0
 
doggzAuthor Commented:
I don't think boolean array will be saved in less than byte[length of boolean array]
0
 
Igor BazarnyCommented:
doggz,

Do you have any comments about my or object's suggestion? More related questions?
0
 
doggzAuthor Commented:
yes, the get by index is great, I need another method which constructs the BitArray like this:
BitArray(int[] values,int[] valSizes, int[] valIndices).

that would be great.
Thanks.
0
 
objectsCommented:
What do valSizes and valIndices represent?
0
 
doggzAuthor Commented:
valSizes is the size in bits that corresponds to the values array, and valIndices is the indices in the required BitArray of rhe corresponding values array.
0
 
Igor BazarnyCommented:
Hi,

Will this help you:

package ee.util;

public class BitArray{
    BitArray(int[] buffer, int usedbits){
        content = new int[buffer.length+1];
        System.arraycopy(buffer,0,content,0,buffer.length);
        used = usedbits;
    }

    BitArray(int[] values, int[] valSizes, int[] valStarts){
        int totalSize = 0;
        for( int i=0; i<valSizes.length; ++i){
            checkIndices(valStarts[i], valStarts[i]+valSizes[i]);
            totalSize = Math.max(totalSize,valStarts[i]+valSizes[i]);
        }
        int arraySize = (totalSize >> 5) + 2;
        content = new int[arraySize];
        used = totalSize;
        for(int i=0; i<values.length; ++i){
            setBits(values[i], valStarts[i], valStarts[i]+valSizes[i]);
        }
    }

    public int getBits(int start, int end){
        checkIndices(start,end);
        int size = end - start;
        int index0 = start >> 5;
        long buffer = ((long)content[index0] << 32) | (0xFFFFFFFFl & content[index0+1]);
        int dropAtStart = start ^ (index0 << 5);
        return (int)( (buffer << dropAtStart) >>> (64-size));
    }

    public void setBits(int value, int start, int end){
        checkIndices(start,end);
        int size = end - start;
        int index0 = start >> 5;
        int innerStart = start ^ (index0 << 5);
        long aligned = (((long) value) << (64-size)) >>> innerStart;
        long mask = ~((0xFFFFFFFFl << (64-size)) >>> innerStart);
        content[index0] &= mask >>> 32;
        content[index0] |= aligned >>> 32;
        if( (mask & 0xFFFFFFFFl) != 0 ){
            content[index0+1] &= mask;
            content[index0+1] |= aligned;
        }
    }

    private void checkIndices(int start, int end){
        int size = end - start;
        if( size < 0 || size >32 ){
            throw new IllegalArgumentException("incorrect size");
        }
        if( end > used ){
            throw new IndexOutOfBoundsException(end+" > "+used);
        }
        if( start < 0 ){
            throw new IndexOutOfBoundsException(start+" < 0");
        }
    }

    public static void main(String[] args){
        int[] buffer = new int[]{0xCAFEBABE,0xDEADBEEF,0x12345678,0xFEDCBA98};
        StringBuffer bitsBuffer = new StringBuffer();
        for(int i=0; i<buffer.length; ++i){
            bitsBuffer.append(binStr(buffer[i]));
        }
        String expected = bitsBuffer.toString();
        BitArray arr = new BitArray(buffer,128);
        for(int i=0; i<=96; ++i){
            String got = binStr(arr.getBits(i,i+32));
            if( !got.equals(expected.substring(i,i+32)) ){
                System.out.println("getBits error at "+i);
            }
        }
        System.out.println("getBits tests passed");

        String setBits = binStr(0xABCD).substring(16);
        for(int i=0; i<=112; ++i){
            arr.setBits(0xABCD,i,i+16);
            String got = binStr(arr.getBits(i,i+16)).substring(16);
            if( !got.equals(setBits) ){
                System.out.println("setBits error at "+i);
            }
        }
        System.out.println("setBits tests passed");

    }

    private static String binStr(int val){
        String tail = Integer.toBinaryString(val);
        if( tail.length() == 32 ){
            return tail;
        }
        StringBuffer head = new StringBuffer(32);
        for(int i = tail.length(); i<32; ++i){
            head.append("0");
        }
        return head.append(tail).toString();
    }
    private int[] content;
    private int used;
}
0
 
doggzAuthor Commented:
I have a small question regarding the setBits().
I think that once I have the aligned number in a long
wouldn't it be ok to do:
long aligned = (((long) value) << (64-size)) >>> innerStart;
content[index0]|=(int)aligned>>32;
content[index0+1]|=(int)aligned;

why do I need the mask for?
0
 
doggzAuthor Commented:
if I understand correctly it is only used to clear the old value of the bits we intend to set.
Thanks.
0
 
doggzAuthor Commented:
really excellent job. Thanks a million.
0
 
Igor BazarnyCommented:
Hi,

Did you get it? I need a mask to preserve bits which should not be changed. Assume you want to set 4 last bits. 28 remaining should be intact, so I need to combine old value with new bits. To do that, I clear bits I want to replace and use 'or' operation to set them to new values.

Also: don't confuse >> and >>> operations. If most significant (sign) bit is set, result will be different-->> expands sign bit, while >>> always fills most significant bits with 0's

Regards,
Igor Bazarny
0
 
doggzAuthor Commented:
one last questions. I noticed that when you allocate the size of the array (int arraySize = (totalSize >> 5) + 2) you add 2. why wouldn't 1 do? I think it would, and then why yet you used 2?
0
 
Igor BazarnyCommented:

I allocate one extra int to simplify calculations. And I don't check whether some bits are left. So, better expression would be: (totalSize >> 5) + ((totalSize & 0x001f) == 0 ? 1 : 2). And with some additional logic (in places where I unconditionally access content[index0+1]) it's possible to remove that extra array element.

So you have some room to improve my solution. I tried to demostrate idea, not optimized solution.
0
 
doggzAuthor Commented:
ok thanks.
0
 
doggzAuthor Commented:
ok thanks.
0

Featured Post

Free Tool: ZipGrep

ZipGrep is a utility that can list and search zip (.war, .ear, .jar, etc) archives for text patterns, without the need to extract the archive's contents.

One of a set of tools we're offering as a way to say thank you for being a part of the community.

  • 10
  • 5
  • 2
  • +2
Tackle projects and never again get stuck behind a technical roadblock.
Join Now