Go Premium for a chance to win a PS4. Enter to Win

x
?
Solved

variable length bit array

Posted on 2002-07-23
19
Medium Priority
?
476 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
Concerto Cloud for Software Providers & ISVs

Can Concerto Cloud Services help you focus on evolving your application offerings, while delivering the best cloud experience to your customers? From DevOps to revenue models and customer support, the answer is yes!

Learn how Concerto can help you.

 
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 2000 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

Concerto's Cloud Advisory Services

Want to avoid the missteps to gaining all the benefits of the cloud? Learn more about the different assessment options from our Cloud Advisory team.

Question has a verified solution.

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

For beginner Java programmers or at least those new to the Eclipse IDE, the following tutorial will show some (four) ways in which you can import your Java projects to your Eclipse workbench. Introduction While learning Java can be done with…
Introduction This article is the first of three articles that explain why and how the Experts Exchange QA Team does test automation for our web site. This article explains our test automation goals. Then rationale is given for the tools we use to a…
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 about basic arrays, how to declare them, and how to use them. Introduction and definition: Declare an array and cover the syntax of declaring them: Initialize every index in the created array: Example/Features of a basic arr…
Suggested Courses

877 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