Solved

variable length bit array

Posted on 2002-07-23
19
450 Views
Last Modified: 2012-05-04
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
Comment
Question by:doggz
  • 10
  • 5
  • 2
  • +2
19 Comments
 
LVL 2

Expert Comment

by:nir2002
ID: 7173614
Hi,

try use: java.math.BigInteger

Best regards
Nir
0
 
LVL 7

Expert Comment

by:Igor Bazarny
ID: 7173812
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
 
LVL 92

Expert Comment

by:objects
ID: 7173939
Have a look at java.util.BitSet class.
 
0
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.

 
LVL 3

Expert Comment

by:yasser_helmy
ID: 7174074
why not use an array of boolean with true meaning 1 and false meaning 0.
0
 

Author Comment

by:doggz
ID: 7174731
I don't think boolean array will be saved in less than byte[length of boolean array]
0
 

Author Comment

by:doggz
ID: 7174758
I don't think boolean array will be saved in less than byte[length of boolean array]
0
 
LVL 7

Expert Comment

by:Igor Bazarny
ID: 7174773
doggz,

Do you have any comments about my or object's suggestion? More related questions?
0
 

Author Comment

by:doggz
ID: 7174798
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
 
LVL 92

Expert Comment

by:objects
ID: 7175885
What do valSizes and valIndices represent?
0
 

Author Comment

by:doggz
ID: 7176306
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
 
LVL 7

Accepted Solution

by:
Igor Bazarny earned 500 total points
ID: 7176420
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
 

Author Comment

by:doggz
ID: 7181749
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
 

Author Comment

by:doggz
ID: 7181802
if I understand correctly it is only used to clear the old value of the bits we intend to set.
Thanks.
0
 

Author Comment

by:doggz
ID: 7181804
really excellent job. Thanks a million.
0
 
LVL 7

Expert Comment

by:Igor Bazarny
ID: 7184413
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
 

Author Comment

by:doggz
ID: 7184500
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
 
LVL 7

Expert Comment

by:Igor Bazarny
ID: 7184549

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
 

Author Comment

by:doggz
ID: 7184560
ok thanks.
0
 

Author Comment

by:doggz
ID: 7184720
ok thanks.
0

Featured Post

Free Tool: IP Lookup

Get more info about an IP address or domain name, such as organization, abuse contacts and geolocation.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Introduction Java can be integrated with native programs using an interface called JNI(Java Native Interface). Native programs are programs which can directly run on the processor. JNI is simply a naming and calling convention so that the JVM (Java…
Basic understanding on "OO- Object Orientation" is needed for designing a logical solution to solve a problem. Basic OOAD is a prerequisite for a coder to ensure that they follow the basic design of OO. This would help developers to understand the b…
Viewers learn about the scanner class in this video and are introduced to receiving user input for their programs. Additionally, objects, conditional statements, and loops are used to help reinforce the concepts. Introduce Scanner class: Importing…
Viewers will learn how to properly install Eclipse with the necessary JDK, and will take a look at an introductory Java program. Download Eclipse installation zip file: Extract files from zip file: Download and install JDK 8: Open Eclipse and …

856 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question