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 is the steps to creating the singular translation.

//Super Fast log 2 calculation over 32 bit integer in right shift each right shift is an 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 bitwies logical version of int32 log 2 without the for loop.
//The n position is multiplied by each single bit that can be 1, or 0 the last active bit is the log 2 size.
//It is possible to rewrite this to use no 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);
}

//Version three is formulated off of Version 2.
//It uses no Multiplication, and has all the shift alignments setup based on each multiply value.
//It is possible to shrink this into an small log 2 function, but at the moment is fairly big.

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 log result.
//It zeros the preceding lower bit positions using XOR so only the highest bit positions create the log number output.

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 ) );
}

//Version 6 checks the bits to 0 then removes preceding bits using "&=" then gives the column value-
//into an single calculation using ternary notation, and using 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 any extra variables and translates the value directly.
//Version 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 one 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 one only outperforms Version 6 when it comes to less then 8 shifts, out of 32.
//Version six is fast no matter which position the binary bits are in the number, and is generally faster.

very cool