Last active
August 3, 2023 17:42
-
-
Save Recoskie/980acb54e9c0a1b6bf7614d47ebc0c46 to your computer and use it in GitHub Desktop.
Super Fast Bitwise Log2, for faster bit lookup algorithams.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
//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. |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
very cool