CODEWITHSUNDEEP
bit-manipulation
Brad
Brad

Reputation: 9223

How to get the most significant non-zero byte in a 32 bit integer without a while loop?

I have a method to extract the most significant, non-zero byte in an integer using the following method: 

private static int getFirstByte(int n)
{
    while (n > 0xFF)
        n >>= 8;

    return n;
}

There's a logic problem with this method. The integer parameter could be negative, which means it would return the number being passed in, which is incorrect.

There is also a possible issue with the method itself. It is using a while loop.

Is there a way to perform this logic without a while loop and also possibly avoiding the incorrectly returned result for negative numbers?

Upvotes: 2

Views: 1885

Answers (3)

paulsm4
paulsm4

Reputation: 121669

Not clever, not elegant - but I believe it does "extract the most significant, non-zero byte in an integer ... without using a loop":

private static int getFirstByte(int n) {
  int i;
  if ((i = n & 0xff000000) != 0)
     return (i >> 24) & 0xff;
  if ((i = n & 0xff0000) != 0)
    return (i >> 16) & 0xff;
  if ((i = n & 0xff00) != 0)
    return (i >> 8) & 0xff;
  // all of the higher bytes are zeroes
  return n;
}

Upvotes: 3

recursion.ninja
recursion.ninja

Reputation: 5488

I assume by get the first non-zero byte in an int you mean natural 8 bit breaks of the int and not a dynamic 8 bit break.

Natural 8 bit breaks:

00000000|00010110|10110010|11110001 ==> 00010110

Dynamic 8 bit break:

00000000000|10110101|1001011110001 ==> 10110101

This will return the first non-zero byte on a natural 8-bit break of an int without looping or branching. This code may or may not be more efficient then paulsm4's answer. Be sure to do benchmarking and/or profiling of the code to determine which is best for you.

Java Code: ideone link

class Main {
    public static void main(String[] args) {
        int i,j;
        for (i=0,j=1; i<32; ++i,j<<=1) {
          System.out.printf("0x%08x : 0x%02x\n",j,getByte(j));
        }
    }
    public static byte getByte(int n) {
        int x = n; 
        x |=   (x >>>  1);
        x |=   (x >>>  2);
        x |=   (x >>>  4);
        x |=   (x >>>  8);
        x |=   (x >>> 16);
        x -=  ((x >>>  1) & 0x55555555);
        x  = (((x >>>  2) & 0x33333333) + (x & 0x33333333));
        x  = (((x >>>  4) + x) & 0x0f0f0f0f);
        x +=   (x >>>  8);
        x +=   (x >>> 16);
        x &= 0x0000003f;
        x  = 32 - x;     // x now equals the number of leading zeros
        x &= 0x00000038; // mask out last 3 bits (cause natural byte break)
        return (byte)((n&(0xFF000000>>>x))>>>(24-x));
    }
}

Upvotes: 2

kmkaplan
kmkaplan

Reputation: 18960

You could use log n / log 256… But then you’d have a bigger problem.

Upvotes: 2

Related Questions