Given a number (bit sequence) and a bit index, how do I find the next highest order bit?

Question

If I have an input, say 51 (00110011) and an index i representing a bit index (ex. i = 0 -> 1, i = 2 -> 0), how to I find a power of 2 like these examples. Sorry, I'm not great with math notation but I can give sample input and output.

Example: If given 51 and index 1 (00110011), I want a function to return 00010000 = 16.

Also, if given 173 and index 2 (10101101), the function must return 00001000 = 8.

I'm looking for a solution that uses bit operations and no loops based on the size of the number preferably.

EDIT: This isn't homework. I'm writing a program that stores user selections as a number. I'm trying to challenge myself here.

Here is what little I've been able to do

    x--;
    for (int j = 0; j < 5; j++) {
        x |= x >> (int) Math.pow(2, i);
    }
    x++;
    return x;

This takes a 32 bit number and returns the next power of 2. I'm not sure if this is of any use though to my problem. I tried seeing if anyone else had posted something similar and this is what I found and thought it might play in to what I'm trying to do.

EDIT 2 I'm having users select days of the week and store those days in a single number. Given a day, I want to find the next day the user has selected. I can easily do that by converting the number to a boolean array but wanted to see if there were any other clever solutions out there. I apologize if it's too "homework" like.

I've realize if I take a number like 51 (00110011) and index 1, I can shave off the first two bits by dividing by 2^1 = 001100. Then, I want the program to find the position of the first 1 (index 2). Then it should return 2^(2+2) because it shaved off 2 bits and the next logical 1 was at index 2 after that.

Where's your attempt? This isn't a homework solving service. — Kon, Jul 25 '16 at 21:27
This isn't homework. I'm writing a program that stored user selections as a number. I'm trying to challenge myself here. — sadelbrid, Jul 25 '16 at 21:27
So then kindly post your attempt at solving this challenge, so we can help you understand what's wrong or missing — Kon, Jul 25 '16 at 21:28
I'll post what little I've worked at and found. Most of my work is on scratch paper in front of me. Hold on... — sadelbrid, Jul 25 '16 at 21:29
Understand that homework has nothing to do with your showing code. Always show it. — Hovercraft Full Of Eels, Jul 25 '16 at 21:31
16 is 2^4, 4 being the location of the next 1 in the bit series — sadelbrid, Jul 25 '16 at 21:37
@keiv.fly Check my edit. I got the notation wrong in the first paragraph. — sadelbrid, Jul 25 '16 at 21:40
Do you really mean `x |= x >> (int) Math.pow(2, i);` ("right shift by 2^i places"), or do you mean `x |= x >> i;` ("right shift by i places")? If it is *really* the former, `x |= x >> (1 << i)` is a better way to write it. — Andy Turner, Jul 25 '16 at 21:53
It sounds like you could do this easily with `java.util.BitSet`. — Andy Turner, Jul 25 '16 at 21:56
According to http://stackoverflow.com/questions/671815/what-is-the-fastest-most-efficient-way-to-find-the-highest-set-bit-msb-in-an-i the solutions that do not use loops are either compiler dependent (GCC) or platform dependent (x86). So on Java you should stay with the loops. — keiv.fly, Jul 25 '16 at 21:57
@AndyTurner I grabbed that from this post here http://stackoverflow.com/questions/1322510/given-an-integer-how-do-i-find-the-next-largest-power-of-two-using-bit-twiddlin It works so it must be the former. Thanks for the advice. I'm new to bit operations — sadelbrid, Jul 25 '16 at 21:58

score 2 · Answer 1 · answered Jul 26 '16 at 12:22

There is a non-loop way too.

There are simple tricks to do things with the lowest set bit, such as setting it to zero or isolating it. In this case, we'll set it to zero:

int x = days & (days - 1);

This works because subtracting one will borrow through the trailing zeroes until it gets to the lowest set bit, which it resets and then the borrowing stops.

If we just need to isolate the now lowest set bit in x, there's a simple trick for that too:

int mask = x & -x;

This works because an alternative way to write -x is ~x + 1, which makes it clear that it will have the "high bits" flipped but the part up to and including the lowest set bit in x remains the same (it got flipped, but then the +1 carries through it flipping it all back).

Likely we also need, at some point, to get the index of that bit. Java has Integer.numberOfTrailingZeros for that, which has a Java implementation that's cleverer way than looping and counting those zeroes one by one, and some one some platforms may be implemented by a native instruction (HotSpot can do this, but of course not necessarily every JVM on every platform can or will do it).

So anyway:

int pos = Integer.numberOfTrailingZeros(x); // note that we can use x here

1000 thanks for pointing out for Integer.numberOfTrailingZeros simple method. — Oleksandr Albul, Dec 19 '18 at 15:41

score 1 · Accepted Answer · answered Jul 25 '16 at 21:48

You have to use a loop anyway. For java, right? The code:

public class Test {
    public static void main(String[] args) {
        System.out.println(yourHomework(51,1));
        System.out.println(yourHomework(173,2));
    }
    public static int yourHomework(int number, int index) { // LOL!! Joke!
            for (int i = index + 1; i < 32; i++) {
                if ((number | (1 << i)) == number)
                     return 1 << i;
            }
            return 0; // Or the value it must return if there is not answer
    }
}

Does this help?. I test it with your cases & it works but I'm not sure this is what you need.

Hey thanks that did the trick! I wasn't sure if there was a simple way to do it without looping or not... Anyways, cheers mate! — sadelbrid, Jul 25 '16 at 21:55

Given a number (bit sequence) and a bit index, how do I find the next highest order bit?

2 Answers2