Solved

variable length bit array

Posted on 2002-07-23
19
430 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
 
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
IT, Stop Being Called Into Every Meeting

Highfive is so simple that setting up every meeting room takes just minutes and every employee will be able to start or join a call from any room with ease. Never be called into a meeting just to get it started again. This is how video conferencing should work!

 

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 Trending Threat Insights Every Day

Enhance your security with threat intelligence from the web. Get trending threat insights on hackers, exploits, and suspicious IP addresses delivered to your inbox with our free Cyber Daily.

Join & Write a Comment

Suggested Solutions

Title # Comments Views Activity
triangle challenge 4 77
count7 challenge 12 69
compre toata in where clue oracle 4 41
maven project error 5 20
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…
In this post we will learn how to connect and configure Android Device (Smartphone etc.) with Android Studio. After that we will run a simple Hello World Program.
Viewers learn about the “while” loop and how to utilize it correctly in Java. Additionally, viewers begin exploring how to include conditional statements within a while loop and avoid an endless loop. Define While Loop: Basic Example: Explanatio…
Viewers will learn one way to get user input in Java. Introduce the Scanner object: Declare the variable that stores the user input: An example prompting the user for input: Methods you need to invoke in order to properly get  user input:

708 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

Need Help in Real-Time?

Connect with top rated Experts

19 Experts available now in Live!

Get 1:1 Help Now