Get bits of a given range more effective?

Question

It's been a while, that I did bit manipulations and I'm not sure if this can be done in a more effective way.

What I want is to get bits of a specific range from a value.
Let's say the binary of the value is: 0b1101101

Now I want to get a 4-bit range from the 2nd to the 5th bit of this value in it's two's complement.
The range I wanna get: 0b1011
Value in Two's complement: -5

This is the code I have, with some thoughts what I'm doing:

public int bitRange(int value, int from, int to) {

    // cut the least significant bits
    value = value >> from;

    // create the mask
    int mask = 0;
    for (int i = from; i <= to; i++) {
        mask = (mask << 1) + 1;
    }

    // extract the bits
    value = value & mask;

    // needed to check the MSB of the range
    int msb = 1 << (to - from);

    // if MSB is 1, XOR and inverse it
    if ((value & msb) == msb ) {
        value = value ^ mask;           
        value = ~value;
    }

    return value;

}

Now I would like to know if this can be done more effective? Especially the creation of the dynamic mask and the check of the MSB of the range, to be able to convert the bit range. Another point is, as user3344003 pointed out correctly, if the range would be 1 bit, the output would be -1. I'm sure there is a possible improvement.

Generally, one only uses unsigned values with bit fields. Think about bitRange (value, 0, 0) ; — user3344003, Oct 22 '14 at 05:27
@user3344003 Yep, would return -1. That's a special case I forgot to mention. — Steve Benett, Oct 22 '14 at 05:29

score 2 · Answer 1 · answered Oct 22 '14 at 05:35

2

For your mask, you could go something like

int mask = 0xffffffff >> 32-(to-from);

Though the chance of that exact code being correct is small. Probably off by one, edge issues, sign problems. But it's on the right track?

answered Oct 22 '14 at 05:35

user949300

15,364
7
35
66

icza · Accepted Answer · 2014-10-22T06:04:52.773

1

Here's your mask:

int mask = 0xffffffff >>> 32 - (to - from + 1);

You have to use >>> due to sign bit is 1.

Another solution could be to store the possible masks which can be 31 values at the most:

private static int[] MASKS = new int[31];
static {
    MASKS[0] = 1;
    for (int i = 1; i < MASKS.length; i++)
        MASKS[i] = (MASKS[i - 1] << 1) + 1;
}

And using this your mask:

int mask = MASKS[to - from];

You can do the same for the msb mask, just store the possible values in a static array, and you don't have to calculate it in your method.

edited Oct 22 '14 at 06:04

answered Oct 22 '14 at 05:48

icza

389,944
63
907
827

Hmm, I was right about off by one and sign issues in my quick initial answer. Thanks for getting it correct. – user949300 Oct 22 '14 at 17:29

Apriori · Answer 3 · 2014-10-24T15:44:25.973

0

Disclaimer: I'm more of a C or C++ programmer, and I know there are some subtles between the bitwise operators in the different languages. But it seems to me that this can be done in one line as follows by taking advantage of the arithmetic shift that will result when shifting a negative value to the right, where one's will be shifted in for the sign extension.

public int bitRange(int value, int from, int to) {
  int waste = 31 - to;
  return (value << waste) >> (waste + from);
}

breakdown:

int a = 31 - to;    // the number of bits to throw away on the left  
int b = value << a; // shift the bits to throw away off the left of the value
int c = a + from;   // the number of bits that now need to be thrown away on the right
int d = b >> c;     // throw bits away on the right, and extend the sign on the left
return d;

edited Oct 24 '14 at 15:44

answered Oct 23 '14 at 15:46

Apriori

2,308
15
16

This produces the same results with less code and operations, which is nice! But there is a flaw, it should be `int waste = 31 - to;`. Anyway, do you know any downsides of this code in comparison to approaches using a mask? Because most advices I've got from different people (not in this question) include using a mask. – Steve Benett Oct 24 '14 at 13:02
Thank you for catching my error (updated). I had little time before having to leave, so none to test but wanted to share. In C and C++ the downside of this would be that people may shake their fingers at you for using arithmetic shift, because technically the language does not guarantee the underlying representation of signed numbers to be two's complement or this to be the shift behavior, though the implementation may. – Apriori Oct 24 '14 at 15:41
However, in practice this is fine, and in Java there are actually two operators (>> and >>>) for the different shifts, see [here](http://stackoverflow.com/questions/2811319/difference-between-and). Given the operators' descriptions, it seems the representation of negative numbers is well defined as two's complement in Java as well. – Apriori Oct 24 '14 at 15:42
So to sum up, no I can't imagine any downsides of this approach given the above. Shifts should all be single cycle operations and therefore fast (On the JVM too I think?), especially considering there are so few operations. However if you're worried about speed nothing compares to to just running the different versions of the code in a tight loop and timing it. – Apriori Oct 24 '14 at 15:42

Get bits of a given range more effective?

3 Answers3