How to do “indexOf” and “lastIndexOf” on an integer with bit flags? (Get the *power* of the found index)

This is a self-answered question I posted on stackoverflow, and is a follow up on my previous question on bit flags, where I cleared up some big misconceptions.

I need to create these functions to find a single bit-flag in an int containing zero or more flags:

BitBinaryUtil
   int twoExponentOfHighestOneBit(int all_flags)

   int twoExponentOfHighestOneBitAtMost(int all_flags,
         int twoExponentOfTwo_max0Thr30Incl)

   int twoExponentOfLowestOneBit(int all_flags)

   int twoExponentOfLowestOneBitAtLeast(int all_flags,
         int twoExponentOfTwo_min0Thr30Incl)

Which are roughly similar to `String.indexOf` and `lastIndexOf`, except they return the *exponent* of two of the found-bit. For example (all 31 bits)

twoExponentOfHighestOneBit:
   1000000000000000000000000000000  -->  30 (2^30=1073741824)
   0000000000000000000000000000001  -->  0  (2^0=1)
   0000000000000100000000000000001  -->  18
   0000000000000000000000000000000  -->  -1

twoExponentOfLowestOneBit:
   1000000000000000000000000000000  -->  30
   0000000000000000000000000000001  -->  0
   0000000000000100000000000000001  -->  0

How can I do this?

This was a brain buster. First, I figured it out with converting the ints to binary strings of length 31 (which is the limit of bit-flags as I understand it):

/**
  <P>Given a 31-bit binary-int, as a string (representing an int with zero or more bit-flags, where the most-significant-bit, the &quot;sign bit&quot;, is removed), get the <I>inverted</I> index of the first one-bit (if the left-most bit is a 1, 31 is the result).</P>

  <P>{@code java InvertedIndexOfHighestOneBitUsingBinaryStrings}</P>
 **/
public class InvertedIndexOfHighestOneBitUsingBinaryStrings  {
  public static final void main(String[] ignored)  {
     //One bit
        test("1000000000000000000000000000000");  //VALUE_OF_31ST_ONE_BIT
        test("0000100000000000000000000000000");
        test("0000000000000000000000000000010");
        test("0000000000000000000000000000000");

     //Two
        test("0110000000000000000000000000000");
        test("0000000000000000000000000000011");
  }
  private static final void test(String int_binStr)  {
     int i = Integer.parseInt(int_binStr, 2);
     System.out.println("31-bits: " + int_binStr + ", int: " + i);

     int exponent = getInvertedIndexHighestOneBit(int_binStr);
     System.out.println("      Highest one-bit is two-to-the-exponent-of: " + exponent);

     if(exponent != -1)  {
        exponent = getInvertedIndexHighestOneBit(int_binStr, (exponent - 1));
        System.out.println("      Next-highest one-bit is two-to-the-exponent-of: " + exponent);
     }
     System.out.println();
  }

Main logic:

  public static final int getInvertedIndexHighestOneBit(String all31Bits_zeroPadded)  {
     return  getInvertedIndexHighestOneBit(all31Bits_zeroPadded, 30);
  }
  public static final int getInvertedIndexHighestOneBit(String all31Bits_zeroPadded, int inverted_startIdx)  {
     int idxFirstOneBit = all31Bits_zeroPadded.indexOf("1", (30 - inverted_startIdx));
     if(idxFirstOneBit == -1)  {
        return  -1;
     }
     return  (30 - idxFirstOneBit);
  }
}

Output:

31-bits: 1000000000000000000000000000000, int: 1073741824
      Highest one-bit is two-to-the-exponent-of: 30
      Next-highest one-bit is two-to-the-exponent-of: -1

31-bits: 0000100000000000000000000000000, int: 67108864
      Highest one-bit is two-to-the-exponent-of: 26
      Next-highest one-bit is two-to-the-exponent-of: -1

31-bits: 0000000000000000000000000000010, int: 2
      Highest one-bit is two-to-the-exponent-of: 1
      Next-highest one-bit is two-to-the-exponent-of: -1

31-bits: 0000000000000000000000000000000, int: 0
      Highest one-bit is two-to-the-exponent-of: -1

31-bits: 0110000000000000000000000000000, int: 805306368
      Highest one-bit is two-to-the-exponent-of: 29
      Next-highest one-bit is two-to-the-exponent-of: 28

31-bits: 0000000000000000000000000000011, int: 3
      Highest one-bit is two-to-the-exponent-of: 1
      Next-highest one-bit is two-to-the-exponent-of: 0

And then I figured it out with bit-manipulation:

 /**
  <P>Given a 31-bit binary-int, as a string (representing an int with zero or more bit-flags, where the most-significant-bit, the &quot;sign bit&quot;, is removed), get the <I>inverted</I> index of the first one-bit (if the left-most bit is a 1, 31 is the result).</P>

  <P>{@code java InvertedIndexOfHighestOneBitUsingInts}</P>
  **/
 public class InvertedIndexOfHighestOneBitUsingInts  {
  public static final int VALUE_OF_31ST_ONE_BIT = Integer.parseInt("1000000000000000000000000000000", 2);
  public static final void main(String[] ignored)  {
     //One bit
        test(VALUE_OF_31ST_ONE_BIT);
        test(Integer.parseInt("0000100000000000000000000000000", 2));
        test(Integer.parseInt("0000000000000000000000000000010", 2));
        test(Integer.parseInt("0000000000000000000000000000000", 2));

     //Two
        test(Integer.parseInt("0110000000000000000000000000000", 2));
        test(Integer.parseInt("0000000000000000000000000000011", 2));
  }
  private static final void test(int num)  {
     System.out.println("Testing: 31-bit binary=" + getIntAsZeroPadded31BitStringNoSign(num) + ", int=" + num);
     int exponent = twoExponentOfHighestOneBit(num);
     System.out.println("   Highest one-bit is two-to-the-exponent-of: " + exponent);
     if(exponent > 0)  {
        System.out.println("   Next-highest one-bit is two-to-the-exponent-of: " + twoExponentOfHighestOneBitAtMost(num, (exponent - 1)));
     }

     exponent = twoExponentOfLowestOneBit(num);
     System.out.println("   Lowest one-bit is two-to-the-exponent-of: " + exponent);
     if(exponent != -1  &&  exponent < 30)  {
        System.out.println("   Next-highest one-bit is two-to-the-exponent-of: " + twoExponentOfLowestOneBitAtLeast(num, (exponent + 1)));
     }
     System.out.println();

  }

Main logic for highest:

  public static final int twoExponentOfHighestOneBit(int all_flags)  {
     return  twoExponentOfHighestOneBitAtMost(all_flags, 30);
  }
  public static final int twoExponentOfHighestOneBitAtMost(int all_flags, int twoExponentOfTwo_max0Thr30Incl)  {
     if(twoExponentOfTwo_max0Thr30Incl < 0  ||  twoExponentOfTwo_max0Thr30Incl > 30)  {
        throw  new IllegalArgumentException("twoExponentOfTwo_max0Thr30Incl (" + twoExponentOfTwo_max0Thr30Incl + ") must be between 1 and 31, inclusive");
     }

     //Index of first one bit:
     int currentBitMask = VALUE_OF_31ST_ONE_BIT >> (30 - twoExponentOfTwo_max0Thr30Incl);
     int exponent = twoExponentOfTwo_max0Thr30Incl;
     while(exponent >= 0)  {
 //System.out.println("   high.currentBitMask=" + getIntAsZeroPadded31BitStringNoSign(currentBitMask) + ", exponent=" + exponent + "");
 //System.out.println("   high.all_flags=     " + getIntAsZeroPadded31BitStringNoSign(all_flags));
        if((all_flags & currentBitMask) == currentBitMask)  {
           return  exponent;
        }
 //System.out.println();
        exponent--;
        currentBitMask >>= 1;
     }
     return  -1;
  }

Main logic for lowest:

  public static final int twoExponentOfLowestOneBit(int all_flags)  {
      return  twoExponentOfLowestOneBitAtLeast(all_flags, 0);
   }
   public static final int twoExponentOfLowestOneBitAtLeast(int all_flags, int twoExponentOfTwo_min0Thr30Incl)  {
      if(twoExponentOfTwo_min0Thr30Incl < 0  ||  twoExponentOfTwo_min0Thr30Incl > 30)  {
         throw  new IllegalArgumentException("twoExponentOfTwo_min0Thr30Incl (" + twoExponentOfTwo_min0Thr30Incl + ") must be between 1 and 30, inclusive.");
      }

      //Index of first one bit:
      int currentBitMask = 1 << twoExponentOfTwo_min0Thr30Incl;
      int exponent = twoExponentOfTwo_min0Thr30Incl;
      while(exponent <= 30)  {
  //System.out.println("   low.currentBitMask=" + getIntAsZeroPadded31BitStringNoSign(currentBitMask) + ", exponent=" + exponent + "");
  //System.out.println("   low.all_flags=     " + getIntAsZeroPadded31BitStringNoSign(all_flags));
         if((all_flags & currentBitMask) == currentBitMask)  {
            return  exponent;
         }
  //System.out.println();
         exponent++;
         currentBitMask <<= 1;
      }
      return  -1;
   }
   public static final String getIntAsZeroPadded31BitStringNoSign(int num)  {
      return  String.format("%32s", Integer.toBinaryString(num)).replace(' ', '0').substring(1, 32);
   }
}

Output:

Testing: 31-bit binary=1000000000000000000000000000000, int=1073741824
   Highest one-bit is two-to-the-exponent-of: 30
   Next-highest one-bit is two-to-the-exponent-of: -1
   Lowest one-bit is two-to-the-exponent-of: 30

Testing: 31-bit binary=0000100000000000000000000000000, int=67108864
   Highest one-bit is two-to-the-exponent-of: 26
   Next-highest one-bit is two-to-the-exponent-of: -1
   Lowest one-bit is two-to-the-exponent-of: 26
   Next-highest one-bit is two-to-the-exponent-of: -1

Testing: 31-bit binary=0000000000000000000000000000010, int=2
   Highest one-bit is two-to-the-exponent-of: 1
   Next-highest one-bit is two-to-the-exponent-of: -1
   Lowest one-bit is two-to-the-exponent-of: 1
   Next-highest one-bit is two-to-the-exponent-of: -1

Testing: 31-bit binary=0000000000000000000000000000000, int=0
   Highest one-bit is two-to-the-exponent-of: -1
   Lowest one-bit is two-to-the-exponent-of: -1

Testing: 31-bit binary=0110000000000000000000000000000, int=805306368
   Highest one-bit is two-to-the-exponent-of: 29
   Next-highest one-bit is two-to-the-exponent-of: 28
   Lowest one-bit is two-to-the-exponent-of: 28
   Next-highest one-bit is two-to-the-exponent-of: 29

Testing: 31-bit binary=0000000000000000000000000000011, int=3
   Highest one-bit is two-to-the-exponent-of: 1
   Next-highest one-bit is two-to-the-exponent-of: 0
   Lowest one-bit is two-to-the-exponent-of: 0
   Next-highest one-bit is two-to-the-exponent-of: 1

Full code:

/**
  <P>Given a 31-bit binary-int, as a string (representing an int with zero or more bit-flags, where the most-significant-bit, the &quot;sign bit&quot;, is removed), get the <I>inverted</I> index of the first one-bit (if the left-most bit is a 1, 31 is the result).</P>

  <P>{@code java InvertedIndexOfHighestOneBitUsingBinaryStrings}</P>
 **/
public class InvertedIndexOfHighestOneBitUsingBinaryStrings  {
  public static final void main(String[] ignored)  {
     //One bit
        test("1000000000000000000000000000000");  //VALUE_OF_31ST_ONE_BIT
        test("0000100000000000000000000000000");
        test("0000000000000000000000000000010");
        test("0000000000000000000000000000000");

     //Two
        test("0110000000000000000000000000000");
        test("0000000000000000000000000000011");
  }
  private static final void test(String int_binStr)  {
     int i = Integer.parseInt(int_binStr, 2);
     System.out.println("31-bits: " + int_binStr + ", int: " + i);

     int exponent = getInvertedIndexHighestOneBit(int_binStr);
     System.out.println("      Highest one-bit is two-to-the-exponent-of: " + exponent);

     if(exponent != -1)  {
        exponent = getInvertedIndexHighestOneBit(int_binStr, (exponent - 1));
        System.out.println("      Next-highest one-bit is two-to-the-exponent-of: " + exponent);
     }
     System.out.println();
  }
  public static final int getInvertedIndexHighestOneBit(String all31Bits_zeroPadded)  {
     return  getInvertedIndexHighestOneBit(all31Bits_zeroPadded, 30);
  }
  public static final int getInvertedIndexHighestOneBit(String all31Bits_zeroPadded, int inverted_startIdx)  {
     int idxFirstOneBit = all31Bits_zeroPadded.indexOf("1", (30 - inverted_startIdx));
     if(idxFirstOneBit == -1)  {
        return  -1;
     }
     return  (30 - idxFirstOneBit);
  }
}
 /**
  <P>Given a 31-bit binary-int, as a string (representing an int with zero or more bit-flags, where the most-significant-bit, the &quot;sign bit&quot;, is removed), get the <I>inverted</I> index of the first one-bit (if the left-most bit is a 1, 31 is the result).</P>

  <P>{@code java InvertedIndexOfHighestOneBitUsingInts}</P>
  **/
 public class InvertedIndexOfHighestOneBitUsingInts  {
  public static final int VALUE_OF_31ST_ONE_BIT = Integer.parseInt("1000000000000000000000000000000", 2);
  public static final void main(String[] ignored)  {
     //One bit
        test(VALUE_OF_31ST_ONE_BIT);
        test(Integer.parseInt("0000100000000000000000000000000", 2));
        test(Integer.parseInt("0000000000000000000000000000010", 2));
        test(Integer.parseInt("0000000000000000000000000000000", 2));

     //Two
        test(Integer.parseInt("0110000000000000000000000000000", 2));
        test(Integer.parseInt("0000000000000000000000000000011", 2));
  }
  private static final void test(int num)  {
     System.out.println("Testing: 31-bit binary=" + getIntAsZeroPadded31BitStringNoSign(num) + ", int=" + num);
     int exponent = twoExponentOfHighestOneBit(num);
     System.out.println("   Highest one-bit is two-to-the-exponent-of: " + exponent);
     if(exponent > 0)  {
        System.out.println("   Next-highest one-bit is two-to-the-exponent-of: " + twoExponentOfHighestOneBitAtMost(num, (exponent - 1)));
     }

     exponent = twoExponentOfLowestOneBit(num);
     System.out.println("   Lowest one-bit is two-to-the-exponent-of: " + exponent);
     if(exponent != -1  &&  exponent < 30)  {
        System.out.println("   Next-highest one-bit is two-to-the-exponent-of: " + twoExponentOfLowestOneBitAtLeast(num, (exponent + 1)));
     }
     System.out.println();

  }
  public static final int twoExponentOfHighestOneBit(int all_flags)  {
     return  twoExponentOfHighestOneBitAtMost(all_flags, 30);
  }
  public static final int twoExponentOfHighestOneBitAtMost(int all_flags, int twoExponentOfTwo_max0Thr30Incl)  {
     if(twoExponentOfTwo_max0Thr30Incl < 0  ||  twoExponentOfTwo_max0Thr30Incl > 30)  {
        throw  new IllegalArgumentException("twoExponentOfTwo_max0Thr30Incl (" + twoExponentOfTwo_max0Thr30Incl + ") must be between 1 and 31, inclusive");
     }

     //Index of first one bit:
     int currentBitMask = VALUE_OF_31ST_ONE_BIT >> (30 - twoExponentOfTwo_max0Thr30Incl);
     int exponent = twoExponentOfTwo_max0Thr30Incl;
     while(exponent >= 0)  {
 //System.out.println("   high.currentBitMask=" + getIntAsZeroPadded31BitStringNoSign(currentBitMask) + ", exponent=" + exponent + "");
 //System.out.println("   high.all_flags=     " + getIntAsZeroPadded31BitStringNoSign(all_flags));
        if((all_flags & currentBitMask) == currentBitMask)  {
           return  exponent;
        }
 //System.out.println();
        exponent--;
        currentBitMask >>= 1;
     }
     return  -1;
  }
  public static final int twoExponentOfLowestOneBit(int all_flags)  {
      return  twoExponentOfLowestOneBitAtLeast(all_flags, 0);
   }
   public static final int twoExponentOfLowestOneBitAtLeast(int all_flags, int twoExponentOfTwo_min0Thr30Incl)  {
      if(twoExponentOfTwo_min0Thr30Incl < 0  ||  twoExponentOfTwo_min0Thr30Incl > 30)  {
         throw  new IllegalArgumentException("twoExponentOfTwo_min0Thr30Incl (" + twoExponentOfTwo_min0Thr30Incl + ") must be between 1 and 30, inclusive.");
      }

      //Index of first one bit:
      int currentBitMask = 1 << twoExponentOfTwo_min0Thr30Incl;
      int exponent = twoExponentOfTwo_min0Thr30Incl;
      while(exponent <= 30)  {
  //System.out.println("   low.currentBitMask=" + getIntAsZeroPadded31BitStringNoSign(currentBitMask) + ", exponent=" + exponent + "");
  //System.out.println("   low.all_flags=     " + getIntAsZeroPadded31BitStringNoSign(all_flags));
         if((all_flags & currentBitMask) == currentBitMask)  {
            return  exponent;
         }
  //System.out.println();
         exponent++;
         currentBitMask <<= 1;
      }
      return  -1;
   }
   public static final String getIntAsZeroPadded31BitStringNoSign(int num)  {
      return  String.format("%32s", Integer.toBinaryString(num)).replace(' ', '0').substring(1, 32);
   }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s