Which bit is on for an integer in Java

Question

I have written this code to check which bits are on of an Integer (if represented in binary) in Java:

public static List<String> list(int val)
{
    List<String> dummyList = new ArrayList<String>();

    int bit = 1;
    int x;

    for(int i=0; i<32; i++)
    {
        x = bit;
        if((x&val)!=0)
            dummyList.add(String.valueOf(i+1));
        bit = bit << 1;
    }

    return dummyList;
}

The above written code works fine. But it has a loop which runs 32 times (In Java integer is 32 bit long). I want to minimize this complexity. Please share the better solution. Thanks in advance.

What are you then *doing* with that list? Do you have any indication that this is actually causing you problems? — Jon Skeet, May 09 '12 at 10:20
well, put a limit on the number of loops using "val"? You know the limit if you know the int — keyser, May 09 '12 at 10:20
What's wrong with making it loop 32 times? Since there's 32 bits, I find it pretty reasonable that to check every bit you should loop 32 times. — Simon Forsberg, May 09 '12 at 10:21
I want to know if there is any better solution to this problem. The loop has to run 32 times. Can I do any bit manipulation so that it gives the list of set bits. Basically I have to reduce the time complexity. @ Jon Skeet : I am using this list to open a file at the index of set bits. — Comet, May 09 '12 at 10:30

score 1 · Answer 1 · answered Apr 22 '13 at 23:08

You could use a bit mask to try to reduce the times through the loop. You add a few operations but potentially do half the looping:

public static List<String> list(int val) {
    List<String> dummyList = new ArrayList<String>();
    int loop = 32;

    // Mask the 16 MSB if all are zero only loop on the 16 LSB
    if((val & 0xFFFF0000) == 0){
        loop = 16;
    }

    int bit = 1;
    int x;

    for (int i = 0; i < loop; i++) {
        x = bit;
        if ((x & val) != 0) {
            dummyList.add(String.valueOf(i + 1));
        }
        bit <<= 1;
    }

    return dummyList;
}

This potentially would increase time depending on the data coming in.

You can also reduce looping in half by doing two bits at a time:

public static List<String> list(int val) {
    List<String> dummyList = new ArrayList<String>();

    int bit = 3;
    int x;

    for (int i = 0; i < 32; i += 2) {
        x = (bit & val);
        switch (x) {
            case 1:
                dummyList.add(String.valueOf(i + 1));
                break;
            case 2:
                dummyList.add(String.valueOf(i+2));
                break;
            case 3:
                dummyList.add(String.valueOf(i+1));
                dummyList.add(String.valueOf(i+2));
                break;
            default:
        }
        val >>= 2;
    }

    return dummyList;
}

score 0 · Answer 2 · answered May 09 '12 at 10:23

0

The complexity is O(1), so there's not much to "minimize" there.

Your code is okay.. here it is refactored slightly.

public static List<String> list(int val) {
    List<String> dummyList = new ArrayList<String>();
    for (int i = 0; i < 32; i++)
        if ((1 << i & val) != 0)
            dummyList.add("" + (i+1));
    return dummyList;
}

Btw, have you considered using a BitSet?

answered May 09 '12 at 10:23

aioobe

413,195
112
811
826

Thanks for the code snippet. I have not considered BitSet. What is the use of BitSet? – Comet May 09 '12 at 10:44
No problem. Will look the documentation. :) – Comet May 09 '12 at 11:13
For the code you have written, will not it take extra time than my code? Because in if ((1 << i & val) != 0) statement for each value of i it will left shift bits in 1 'i' times and hence will take extra time. (For i=30, it will left shift 1 30 times and again for i=31 it will left shift 1 31 times). In my code total left shift is 32 only and in your code it's 1+2+3+... – Comet May 09 '12 at 18:53
Depends on the compiler at hand, the jvm at hand, and the jit compiler. If you're worried about it, why don't you unroll the loop manually – aioobe May 09 '12 at 19:28
The only difference I can see is that you have removed the extra variable which i had used. Which is good as it will save some bytes, but I don't think shifting i times in each cycle is good. In your code you are using left shift ~450 times which was 32 in my case. Anyway the mix code can be prepared which will remove both deficiency. :) – Comet May 09 '12 at 20:39
@Comet On modern hardware it should not make any difference (in terms of time spent) if you do `x << 1` or `x << 30`, see [this question](http://stackoverflow.com/q/4234120/1347968). – siegi Sep 22 '12 at 11:28

score 0 · Answer 3 · answered May 09 '12 at 10:24

0

32 loops sounds good for this application. You can use a StringBuffer instead of List if you want to collect the digits faster.

public static String list(int val)
{
    StringBuffer dummyList = new StringBuffer();

    int bit = 1;
    int x;

    for(int i=0; i<32; i++)
    {
        x = bit;
        dummyList.append((x&val) ? '1' : '0' );
        bit = bit << 1;
    }

    return dummyList.toString();
}

answered May 09 '12 at 10:24

alexg

3,015
3
23
36

Thanks for the code snippet and for your suggestion to use StringBuffer. But for further processing I needed to make use of methods already defined in List class, that is why I used List<>. – Comet May 09 '12 at 10:37
Are you trying to reduce algorithmic complexity or wall-clock time? If you do some tests you might find that your assumptions about what is faster is wrong. Depends on what you want the output format of your function to be. I wonder if maybe you're trying to put the file handles on a Map, in which case it might be a better idea to extend your file handle with a custom hashCode and use a HashMap. Tell us more about what you're trying to do and why :) – alexg May 09 '12 at 10:44
I have one file (say X) which contains ~3000 values one in each line. There are more than 2000 files (say Y's) which consists those values. For my application I have to figure out what values are common between two files. Because the value set is large, it is not feasible to check one by one. So I did preprocessing. Initially I indexed values in file X from 1 to 3000. Then I made groups of 30 values (for eg. 0-29 is group 1, 30-59 group 2 and so on). Then instead of writing values in Y’s, I wrote in the format ( ). – Comet May 09 '12 at 11:10
This new value can be represented in the form of power of 2. Suppose in file “Y” for group 1 the present value were 1st and 3rd, then the new value will be 5 (first and third bit on). Now in each Y’s I will have maximum 100 lines which was ~3000 earlier. Now for two files I can check for same group number first and then calculate actual values. I have done 2nd level indexing too but that is not important here. Let me know if I'm not clear or missing the point. – Comet May 09 '12 at 11:10
@Comet looks like the XY-problem. Why don't you make a question about fast solutions your actual problem, instead of about a solution you think you should use? Also, converting bits in an int to a list seems suspicious to me - there should probably be a bit-math solution. – harold May 09 '12 at 12:45
@harold : The core problem remains same as I could not think of any better solution of the problem. Please share any better solution of the above given problem. I shall be highly thankful. – Comet May 09 '12 at 18:47

recursion.ninja · Answer 4 · 2013-02-23T22:00:54.890

Improving O(1) code seems trivial but this code is a slight improvement:

public static List<String> list(int val) {
    List<String> dummyList = new ArrayList<String>();
    for (int i=0; val!=0 && i<32; ++i){
        if ((1 << i & val) != 0) {
            dummyList.add("" + (i+1));
            val &= val -1;  // unset the last set bit (current bit)
        }                   // causes loop to end early when all bits are counted
    }
    return dummyList;

Rather then making all 32 bit comparisons, this code will end as soon as the last bit has been counted. It is much more efficient for integers that are sparsely populated with 1s and no less efficient for integers which are highly populated.

score 0 · Answer 5 · answered Feb 02 '13 at 02:51

Since you know the exact length of the integer I would recommend using a bool[] instead. There is not much you can do about the complexity though. It is as fast as it can get and the JIT is probably going to unroll the loop of this code anyways.

public static bool[] list(int val)
{
    bool[] a = new bool[32];
    for(int i=0; i<32; i++)
    {
        a[i] = ((1 << i) & val) != 0;
    }
    return a;
}

Which bit is on for an integer in Java

5 Answers5