Super Fast Bitwise Log2, for faster bit lookup algorithams.

Bitwise Log2.js

//Note method 6 is an single line using only logical and, and or it is the fastest method.
//This document contains the steps to create the singular translation.

//Super Fast log 2 calculation over 32-bit integer in right shift. Each right shift is a division of 2 in binary.

function Log2_Int32_V1(V)
{
  for( var n = 31; n > 0; V >>> n ? ( V = n, n = 0 ) : n-- );
  return(V);
}

//Version two is the bitwise logical version of int32 log 2 without the for loop.
//The n position is multiplied by every single bit that can be 1 or 0. The last active bit is the log 2 size.
//It is possible to rewrite this without multiplication.
//It then is possible to line up the shifts as the log 2 result.
//It is possible to shrink this into the fastest log 2 function that will ever be made.

function Log2_Int32_V2(V)
{
  var n = 1, R = 0;

  R = ( ( ~( V >> n ) & 1 ) * R ) | ( ( V >> n ) & 1 ) * n++;
  R = ( ( ~( V >> n ) & 1 ) * R ) | ( ( V >> n ) & 1 ) * n++;
  R = ( ( ~( V >> n ) & 1 ) * R ) | ( ( V >> n ) & 1 ) * n++;
  R = ( ( ~( V >> n ) & 1 ) * R ) | ( ( V >> n ) & 1 ) * n++;
  R = ( ( ~( V >> n ) & 1 ) * R ) | ( ( V >> n ) & 1 ) * n++;
  R = ( ( ~( V >> n ) & 1 ) * R ) | ( ( V >> n ) & 1 ) * n++;
  R = ( ( ~( V >> n ) & 1 ) * R ) | ( ( V >> n ) & 1 ) * n++;
  R = ( ( ~( V >> n ) & 1 ) * R ) | ( ( V >> n ) & 1 ) * n++;
  R = ( ( ~( V >> n ) & 1 ) * R ) | ( ( V >> n ) & 1 ) * n++;
  R = ( ( ~( V >> n ) & 1 ) * R ) | ( ( V >> n ) & 1 ) * n++;
  R = ( ( ~( V >> n ) & 1 ) * R ) | ( ( V >> n ) & 1 ) * n++;
  R = ( ( ~( V >> n ) & 1 ) * R ) | ( ( V >> n ) & 1 ) * n++;
  R = ( ( ~( V >> n ) & 1 ) * R ) | ( ( V >> n ) & 1 ) * n++;
  R = ( ( ~( V >> n ) & 1 ) * R ) | ( ( V >> n ) & 1 ) * n++;
  R = ( ( ~( V >> n ) & 1 ) * R ) | ( ( V >> n ) & 1 ) * n++;
  R = ( ( ~( V >> n ) & 1 ) * R ) | ( ( V >> n ) & 1 ) * n++;
  R = ( ( ~( V >> n ) & 1 ) * R ) | ( ( V >> n ) & 1 ) * n++;
  R = ( ( ~( V >> n ) & 1 ) * R ) | ( ( V >> n ) & 1 ) * n++;
  R = ( ( ~( V >> n ) & 1 ) * R ) | ( ( V >> n ) & 1 ) * n++;
  R = ( ( ~( V >> n ) & 1 ) * R ) | ( ( V >> n ) & 1 ) * n++;
  R = ( ( ~( V >> n ) & 1 ) * R ) | ( ( V >> n ) & 1 ) * n++;
  R = ( ( ~( V >> n ) & 1 ) * R ) | ( ( V >> n ) & 1 ) * n++;
  R = ( ( ~( V >> n ) & 1 ) * R ) | ( ( V >> n ) & 1 ) * n++;
  R = ( ( ~( V >> n ) & 1 ) * R ) | ( ( V >> n ) & 1 ) * n++;
  R = ( ( ~( V >> n ) & 1 ) * R ) | ( ( V >> n ) & 1 ) * n++;
  R = ( ( ~( V >> n ) & 1 ) * R ) | ( ( V >> n ) & 1 ) * n++;
  R = ( ( ~( V >> n ) & 1 ) * R ) | ( ( V >> n ) & 1 ) * n++;
  R = ( ( ~( V >> n ) & 1 ) * R ) | ( ( V >> n ) & 1 ) * n++;
  R = ( ( ~( V >> n ) & 1 ) * R ) | ( ( V >> n ) & 1 ) * n++;
  R = ( ( ~( V >> n ) & 1 ) * R ) | ( ( V >> n ) & 1 ) * n++;
  R = ( ( ~( V >> n ) & 1 ) * R ) | ( ( V >> n ) & 1 ) * n++;

  return(R);
}

/*This creates the following table for all input and output
(We could have started with a table showing
what we want all inputs to be and what we want the outputs to be.
However, I thought showing the original log2 function would
be interesting to the developer). We call these "truth tables".
+--------------------------------+--------------------------------+
|              Input             |              Output            |
+--------------------------------+--------------------------------+
|00000000000000000000000000000001|00000000000000000000000000000000|
|00000000000000000000000000000010|00000000000000000000000000000001|
|00000000000000000000000000000100|00000000000000000000000000000010|
|00000000000000000000000000001000|00000000000000000000000000000011|
|00000000000000000000000000010000|00000000000000000000000000000100|
|00000000000000000000000000100000|00000000000000000000000000000101|
|00000000000000000000000001000000|00000000000000000000000000000110|
|00000000000000000000000010000000|00000000000000000000000000000111|
|00000000000000000000000100000000|00000000000000000000000000001001|
|00000000000000000000001000000000|00000000000000000000000000001010|
|00000000000000000000010000000000|00000000000000000000000000001011|
|00000000000000000000100000000000|00000000000000000000000000001100|
|00000000000000000001000000000000|00000000000000000000000000001101|
|00000000000000000010000000000000|00000000000000000000000000001110|
|00000000000000000100000000000000|00000000000000000000000000001111|
|00000000000000001000000000000000|00000000000000000000000000010000|
|00000000000000010000000000000000|00000000000000000000000000010001|
|00000000000000100000000000000000|00000000000000000000000000010010|
|00000000000001000000000000000000|00000000000000000000000000010011|
|00000000000010000000000000000000|00000000000000000000000000010100|
|00000000000100000000000000000000|00000000000000000000000000010101|
|00000000001000000000000000000000|00000000000000000000000000010110|
|00000000010000000000000000000000|00000000000000000000000000010111|
|00000000100000000000000000000000|00000000000000000000000000011000|
|00000001000000000000000000000000|00000000000000000000000000011001|
|00000010000000000000000000000000|00000000000000000000000000011010|
|00000100000000000000000000000000|00000000000000000000000000011011|
|00001000000000000000000000000000|00000000000000000000000000011100|
|00010000000000000000000000000000|00000000000000000000000000011101|
|00100000000000000000000000000000|00000000000000000000000000011110|
|01000000000000000000000000000000|00000000000000000000000000011111|
|10000000000000000000000000000000|00000000000000000000000000100000|
+--------------------------------+--------------------------------+
Now, we use three gates and three steps to convert inputs to outputs into code.
-------------------------------------------------------------------
We will call our first input "V" in the data function.
We use "NOT = ~" to flip all zeros to ones in input "V" and store the result in a separate value called "Vr".
This allows us to compare any combination of ones and zeros.
Example 1011 becomes "V and Vr and V and V" = 1 under the combination 1011.
We still have to move the value left or to the right using shift operations <<, and >> to compare each digit (1, and 0).
Now if we want this one output to be, say, 1001, then we move this one output to the left three times (<< 3) to
make 1000 and to the left zero times to make 0001. We combine 1000 and 0001 using "OR" (1000 | 0001 = 1001).
We combine all individual lines for all inputs to output using "OR" to create the maximally expanded form of our function
from given inputs to output using the "truth table".*/

/*Version 3 is formulated off of Version 2 (Truth table).
It uses no Multiplication and has all the shift alignments set up based on each value.
It is possible to shrink this into a small log 2 function, but
at the moment, it is the maximumly expanded version of
the inputs to output of the given data function.*/

function Log2_Int32_V3(V)
{
  var Vr = ~V, R = 0;

  R = ( ( V >> 1 ) & 1 );
  R = ( ( - ( ( Vr >> 2 ) & 1 ) ) & R ) | ( ( V >> 1 ) & 2 );
  R = ( ( - ( ( Vr >> 3 ) & 1 ) ) & R ) | ( ( ( V >> 2 ) & 2 ) | ( ( V >> 3 ) & 1 ) );
  R = ( ( - ( ( Vr >> 4 ) & 1 ) ) & R ) | ( ( ( V >> 2 ) & 4 ) );
  R = ( ( - ( ( Vr >> 5 ) & 1 ) ) & R ) | ( ( ( V >> 3 ) & 4 ) | ( ( V >> 5 ) & 1 ) );
  R = ( ( - ( ( Vr >> 6 ) & 1 ) ) & R ) | ( ( ( V >> 4 ) & 4 ) | ( ( V >> 5 ) & 2 ) );
  R = ( ( - ( ( Vr >> 7 ) & 1 ) ) & R ) | ( ( ( V >> 5 ) & 4 ) | ( ( V >> 6 ) & 2 ) | ( ( V >> 7 ) & 1 ) );
  R = ( ( - ( ( Vr >> 8 ) & 1 ) ) & R ) | ( ( ( V >> 5 ) & 8 ) );
  R = ( ( - ( ( Vr >> 9 ) & 1 ) ) & R ) | ( ( ( V >> 6 ) & 8 ) | ( ( V >> 9 ) & 1 ) );
  R = ( ( - ( ( Vr >> 10 ) & 1 ) ) & R ) | ( ( ( V >> 7 ) & 8 ) | ( ( V >> 9 ) & 2 ) );
  R = ( ( - ( ( Vr >> 11 ) & 1 ) ) & R ) | ( ( ( V >> 8 ) & 8 ) | ( ( V >> 10 ) & 2 ) | ( ( V >> 11 ) & 1 ) );
  R = ( ( - ( ( Vr >> 12 ) & 1 ) ) & R ) | ( ( ( V >> 9 ) & 8 ) | ( ( V >> 10 ) & 4 ) );
  R = ( ( - ( ( Vr >> 13 ) & 1 ) ) & R ) | ( ( ( V >> 10 ) & 8 ) | ( ( V >> 11 ) & 4 ) | ( ( V >> 13 ) & 1 ) );
  R = ( ( - ( ( Vr >> 14 ) & 1 ) ) & R ) | ( ( ( V >> 11 ) & 8 ) | ( ( V >> 12 ) & 4 ) | ( ( V >> 13 ) & 2 ) );
  R = ( ( - ( ( Vr >> 15 ) & 1 ) ) & R ) | ( ( ( V >> 12 ) & 8 ) | ( ( V >> 13 ) & 4 ) | ( ( V >> 14 ) & 2 ) | ( ( V >> 15 ) & 1 ) );
  R = ( ( - ( ( Vr >> 16 ) & 1 ) ) & R ) | ( ( ( V >> 12 ) & 16 ) );
  R = ( ( - ( ( Vr >> 17 ) & 1 ) ) & R ) | ( ( ( V >> 13 ) & 16 ) | ( ( V >> 17 ) & 1 ) );
  R = ( ( - ( ( Vr >> 18 ) & 1 ) ) & R ) | ( ( ( V >> 14 ) & 16 ) | ( ( V >> 17 ) & 2 ) );
  R = ( ( - ( ( Vr >> 19 ) & 1 ) ) & R ) | ( ( ( V >> 15 ) & 16 ) | ( ( V >> 18 ) & 2 ) | ( ( V >> 19 ) & 1 ) );
  R = ( ( - ( ( Vr >> 20 ) & 1 ) ) & R ) | ( ( ( V >> 16 ) & 16 ) | ( ( V >> 18 ) & 4 ) );
  R = ( ( - ( ( Vr >> 21 ) & 1 ) ) & R ) | ( ( ( V >> 17 ) & 16 ) | ( ( V >> 19 ) & 4 ) | ( ( V >> 21 ) & 1 ) );
  R = ( ( - ( ( Vr >> 22 ) & 1 ) ) & R ) | ( ( ( V >> 18 ) & 16 ) | ( ( V >> 20 ) & 4 ) | ( ( V >> 21 ) & 2 ) );
  R = ( ( - ( ( Vr >> 23 ) & 1 ) ) & R ) | ( ( ( V >> 19 ) & 16 ) | ( ( V >> 21 ) & 4 ) | ( ( V >> 22 ) & 2 ) | ( ( V >> 23 ) & 1 ) );
  R = ( ( - ( ( Vr >> 24 ) & 1 ) ) & R ) | ( ( ( V >> 20 ) & 16 ) | ( ( V >> 21 ) & 8 ) );
  R = ( ( - ( ( Vr >> 25 ) & 1 ) ) & R ) | ( ( ( V >> 21 ) & 16 ) | ( ( V >> 22 ) & 8 ) | ( ( V >> 25 ) & 1 ) );
  R = ( ( - ( ( Vr >> 26 ) & 1 ) ) & R ) | ( ( ( V >> 22 ) & 16 ) | ( ( V >> 23 ) & 8 ) | ( ( V >> 25 ) & 2 ) );
  R = ( ( - ( ( Vr >> 27 ) & 1 ) ) & R ) | ( ( ( V >> 23 ) & 16 ) | ( ( V >> 24 ) & 8 ) | ( ( V >> 26 ) & 2 ) | ( ( V >> 27 ) & 1 ) );
  R = ( ( - ( ( Vr >> 28 ) & 1 ) ) & R ) | ( ( ( V >> 24 ) & 16 ) | ( ( V >> 25 ) & 8 ) | ( ( V >> 26 ) & 4 ) );
  R = ( ( - ( ( Vr >> 29 ) & 1 ) ) & R ) | ( ( ( V >> 25 ) & 16 ) | ( ( V >> 26 ) & 8 ) | ( ( V >> 27 ) & 4 ) | ( ( V >> 29 ) & 1 ) );
  R = ( ( - ( ( Vr >> 30 ) & 1 ) ) & R ) | ( ( ( V >> 26 ) & 16 ) | ( ( V >> 27 ) & 8 ) | ( ( V >> 28 ) & 4 ) | ( ( V >> 29 ) & 2 ) );
  R = ( ( - ( ( Vr >> 31 ) & 1 ) ) & R ) | ( ( ( V >> 27 ) & 16 ) | ( ( V >> 28 ) & 8 ) | ( ( V >> 29 ) & 4 ) | ( ( V >> 30 ) & 2 ) | ( ( V >> 31 ) & 1 ) );

  return(R);
}

//Version 4 single line bitwise log 2 calculation.

function Log2_Int32_V4(V)
{
  var Vr = ~V, R = 0;

  R = ( ( Vr >> 31 ) & ( ( ( ( Vr << 1 ) >> 31 ) & ( ( ( ( Vr << 2 ) >> 31 ) & ( ( ( ( Vr << 3 ) >> 31 ) & ( ( ( ( Vr << 4 ) >> 31 ) & ( ( ( ( Vr << 5 ) >> 31 ) & ( ( ( ( Vr << 6 ) >> 31 ) & ( ( ( ( Vr << 7 ) >> 31 ) & ( ( ( ( Vr << 8 ) >> 31 ) & ( ( ( ( Vr << 9 ) >> 31 ) & ( ( ( ( Vr << 10 ) >> 31 ) & ( ( ( ( Vr << 11 ) >> 31 ) & ( ( ( ( Vr << 12 ) >> 31 ) & ( ( ( ( Vr << 13 ) >> 31 ) & ( ( ( ( Vr << 14 ) >> 31 ) & ( ( ( ( Vr << 15 ) >> 31 ) & ( ( ( ( Vr << 16 ) >> 31 ) & ( ( ( ( Vr << 17 ) >> 31 ) & ( ( ( ( Vr << 18 ) >> 31 ) & ( ( ( ( Vr << 19 ) >> 31 ) & ( ( ( ( Vr << 20 ) >> 31 ) & ( ( ( ( Vr << 21 ) >> 31 ) & ( ( ( ( Vr << 22 ) >> 31 ) & ( ( ( ( Vr << 23 ) >> 31 ) & ( ( ( ( Vr << 24 ) >> 31 ) & ( ( ( ( Vr << 25 ) >> 31 ) & ( ( ( ( Vr << 26 ) >> 31 ) & ( ( ( ( Vr << 27 ) >> 31 ) & ( ( ( ( Vr << 28 ) >> 31 ) & ( ( ( ( Vr << 29 ) >> 31 ) & ( ( V >> 1 ) & 1 ) ) | ( ( V >> 1 ) & 2 ) ) ) | ( ( ( V >> 2 ) & 2 ) | ( ( V >> 3 ) & 1 ) ) ) ) | ( ( ( V >> 2 ) & 4 ) ) ) ) | ( ( ( V >> 3 ) & 4 ) | ( ( V >> 5 ) & 1 ) ) ) ) | ( ( ( V >> 4 ) & 4 ) | ( ( V >> 5 ) & 2 ) ) ) ) | ( ( ( V >> 5 ) & 4 ) | ( ( V >> 6 ) & 2 ) | ( ( V >> 7 ) & 1 ) ) ) ) | ( ( ( V >> 5 ) & 8 ) ) ) ) | ( ( ( V >> 6 ) & 8 ) | ( ( V >> 9 ) & 1 ) ) ) ) | ( ( ( V >> 7 ) & 8 ) | ( ( V >> 9 ) & 2 ) ) ) ) | ( ( ( V >> 8 ) & 8 ) | ( ( V >> 10 ) & 2 ) | ( ( V >> 11 ) & 1 ) ) ) ) | ( ( ( V >> 9 ) & 8 ) | ( ( V >> 10 ) & 4 ) ) ) ) | ( ( ( V >> 10 ) & 8 ) | ( ( V >> 11 ) & 4 ) | ( ( V >> 13 ) & 1 ) ) ) ) | ( ( ( V >> 11 ) & 8 ) | ( ( V >> 12 ) & 4 ) | ( ( V >> 13 ) & 2 ) ) ) ) | ( ( ( V >> 12 ) & 8 ) | ( ( V >> 13 ) & 4 ) | ( ( V >> 14 ) & 2 ) | ( ( V >> 15 ) & 1 ) ) ) ) | ( ( ( V >> 12 ) & 16 ) ) ) ) | ( ( ( V >> 13 ) & 16 ) | ( ( V >> 17 ) & 1 ) ) ) ) | ( ( ( V >> 14 ) & 16 ) | ( ( V >> 17 ) & 2 ) ) ) ) | ( ( ( V >> 15 ) & 16 ) | ( ( V >> 18 ) & 2 ) | ( ( V >> 19 ) & 1 ) ) ) ) | ( ( ( V >> 16 ) & 16 ) | ( ( V >> 18 ) & 4 ) ) ) ) | ( ( ( V >> 17 ) & 16 ) | ( ( V >> 19 ) & 4 ) | ( ( V >> 21 ) & 1 ) ) ) ) | ( ( ( V >> 18 ) & 16 ) | ( ( V >> 20 ) & 4 ) | ( ( V >> 21 ) & 2 ) ) ) ) | ( ( ( V >> 19 ) & 16 ) | ( ( V >> 21 ) & 4 ) | ( ( V >> 22 ) & 2 ) | ( ( V >> 23 ) & 1 ) ) ) ) | ( ( ( V >> 20 ) & 16 ) | ( ( V >> 21 ) & 8 ) ) ) ) | ( ( ( V >> 21 ) & 16 ) | ( ( V >> 22 ) & 8 ) | ( ( V >> 25 ) & 1 ) ) ) ) | ( ( ( V >> 22 ) & 16 ) | ( ( V >> 23 ) & 8 ) | ( ( V >> 25 ) & 2 ) ) ) ) | ( ( ( V >> 23 ) & 16 ) | ( ( V >> 24 ) & 8 ) | ( ( V >> 26 ) & 2 ) | ( ( V >> 27 ) & 1 ) ) ) ) | ( ( ( V >> 24 ) & 16 ) | ( ( V >> 25 ) & 8 ) | ( ( V >> 26 ) & 4 ) ) ) ) | ( ( ( V >> 25 ) & 16 ) | ( ( V >> 26 ) & 8 ) | ( ( V >> 27 ) & 4 ) | ( ( V >> 29 ) & 1 ) ) ) ) | ( ( ( V >> 26 ) & 16 ) | ( ( V >> 27 ) & 8 ) | ( ( V >> 28 ) & 4 ) | ( ( V >> 29 ) & 2 ) ) ) ) | ( ( ( V >> 27 ) & 16 ) | ( ( V >> 28 ) & 8 ) | ( ( V >> 29 ) & 4 ) | ( ( V >> 30 ) & 2 ) | ( ( V >> 31 ) & 1 ) );

  return(R);
}

//Version 5 shrinks the bit patterns from version 4 for each bit that forums the number for the result.

function Log2_Int32_V5( V )
{
  var N16 = 0, N8 = 0, N4 = 0, N2 = 0, N1 = 0;

  V ^= ( ( V & 0x0000FFFF ) & ( N16 = ( ( ( V & 0xFFFF0000 ) | ( ~( V & 0xFFFF0000 ) + 1 ) ) >> 31 ) ) );
  V ^= ( ( V & 0x00FF00FF ) & ( N8 = ( ( ( V & 0xFF00FF00 ) | ( ~( V & 0xFF00FF00 ) + 1 ) ) >> 31 ) ) );
  V ^= ( ( V & 0x0F0F0F0F ) & ( N4 = ( ( ( V & 0xF0F0F0F0 ) | ( ~( V & 0xF0F0F0F0 ) + 1 ) ) >> 31 ) ) );
  V ^= ( ( V & 0x33333333 ) & ( N2 = ( ( ( V & 0xCCCCCCCC ) | ( ~( V & 0xCCCCCCCC ) + 1 ) ) >> 31 ) ) );
  N1 = ( ( ( V & 0xAAAAAAAA ) | ( ~( V & 0xAAAAAAAA ) + 1 ) ) >> 31 );

  return ( ( N16 & 16 ) | ( N8 & 8 ) | ( N4 & 4 ) | ( N2 & 2 ) | ( N1 & 1 ) );
}

/*This can still be further reduced by removing combinations that are the same as the math operations.
All math operations can be constructed from just a "truth table" in maximumly expanded form and
shrunk to the smallest version as well, so all math operations are combinations of "AND", "OR", and "NOT".
We can remove the relative math combinations to make the function smaller and faster.
It has an equal to 0 comparison.
See https://gist.github.com/Recoskie/de34fad9c803c670795ba85d721008c8#file-alu-js

Version 6 checks the bits to 0, then removes preceding bits using "&=" then gives the column value-
into a single calculation using ternary notation and logical or to put the number together.
This version is faster than the previous methods and is most likely the fastest way.
It does not define extra variables and directly translates the value.
Versions one and six are the fastest methods. Technically, version 6 is the best overall when tested.*/

function Log2_Int32_V6( V )
{
  return( ( ( V & 0xFFFF0000 ) !== 0 ? ( V &= 0xFFFF0000, 16 ) : 0 ) | ( ( V & 0xFF00FF00 ) !== 0 ? ( V &= 0xFF00FF00, 8 ) : 0 ) | ( ( V & 0xF0F0F0F0 ) !== 0 ? ( V &= 0xF0F0F0F0, 4 ) : 0 ) | ( ( V & 0xCCCCCCCC ) !== 0 ? ( V &= 0xCCCCCCCC, 2 ) : 0 ) | ( ( V & 0xAAAAAAAA ) !== 0 ) );
}

/*Version 1 is faster when the highest binary bit is set one as it only has to shift once, but the further down the
bit is, the slower it gets.
Version 1 only outperforms Version 6 when it comes to less than 8 shifts out of 32.
Version 6 is fast no matter which position the binary bits are in the number and is generally faster.*/

/*This document shows how to take raw data apart or functions with multiple inputs and outputs, put them in maximally
expanded form, and shrink them back down into the smallest possible function/calculations.
Although log2 is just one input and output. This reduction method works with more than one input and output.*/

/*In reality, we can convert anything from any given inputs to outputs back into the simplest function using this form of
comparison and reduction.
Companies like Intel and AMD already use such technologies that do the conversions for them to help build
ultra-optimized codes and computer hardware.
As this has been revealed to you, you must remember that great power comes with great responsibility.
This allows you to take anything apart by knowing the inputs and outputs, including reality itself and every
math therom we have. It also allows you to see everything going on in raw data.*/

very cool