Last active
September 21, 2025 01:23
-
-
Save leodutra/63ca94fe86dcffee1bab to your computer and use it in GitHub Desktop.
Fast Int Math + Bitwise Hacks For JavaScript
This file contains hidden or 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
| /** | |
| * Bitwise Mathematics Utilities | |
| * | |
| * A collection of fast bitwise operations for integer mathematics. | |
| * These functions prioritize performance over readability and should be used | |
| * when micro-optimizations are critical (game engines, real-time applications). | |
| * | |
| * References: | |
| * - http://michalbe.blogspot.com.br/2013/03/javascript-less-known-parts-bitwise.html | |
| * - http://jsperf.com/bitwise-vs-math-object | |
| * - http://united-coders.com/christian-harms/results-for-game-for-forfeits-and-the-winner-is/ | |
| * - https://mudcu.be/journal/2011/11/bitwise-gems-and-other-optimizations/ | |
| * - https://dreaminginjavascript.wordpress.com/2009/02/09/bitwise-byte-foolish/ | |
| * - http://jsperf.com/math-min-max-vs-ternary-vs-if/24 | |
| * - https://graphics.stanford.edu/~seander/bithacks.html | |
| * - https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Bitwise_Operators | |
| */ | |
| "use strict"; | |
| // ============================================================================ | |
| // CONSTANTS | |
| // ============================================================================ | |
| const PI = Math.PI; | |
| const HALF_PI = PI * 0.5; | |
| const TWO_PI = PI * 2; | |
| const RADIAN = 180 / PI; | |
| // 32-bit signed integer limits for bitwise operations | |
| const MAX_SIGNED_32_BIT_INT = 0x7FFFFFFF; // 2^31 - 1 | |
| const MIN_SIGNED_32_BIT_INT = -0x80000000; // -2^31 | |
| // Ensure ES6 safe integer constants exist | |
| if (typeof Number.MAX_SAFE_INTEGER === 'undefined') { | |
| Number.MAX_SAFE_INTEGER = 0x1FFFFFFFFFFFFF; // 2^53 - 1 | |
| Number.MIN_SAFE_INTEGER = -Number.MAX_SAFE_INTEGER; | |
| } | |
| // ============================================================================ | |
| // BASIC ARITHMETIC OPERATIONS | |
| // ============================================================================ | |
| /** | |
| * Fast absolute value for 32-bit signed integers | |
| * Uses bit manipulation to avoid branching | |
| * @param {number} n - Integer to get absolute value of | |
| * @returns {number} Absolute value of n | |
| */ | |
| function absInt(n) { | |
| const mask = n >> 31; | |
| return (n ^ mask) - mask; | |
| } | |
| /** | |
| * Fast maximum of two 32-bit signed integers | |
| * @param {number} a - First integer | |
| * @param {number} b - Second integer | |
| * @returns {number} Maximum of a and b | |
| */ | |
| function maxInt(a, b) { | |
| return a - ((a - b) & ((a - b) >> 31)); | |
| } | |
| /** | |
| * Fast minimum of two 32-bit signed integers | |
| * @param {number} a - First integer | |
| * @param {number} b - Second integer | |
| * @returns {number} Minimum of a and b | |
| */ | |
| function minInt(a, b) { | |
| return a - ((a - b) & ((b - a) >> 31)); | |
| } | |
| /** | |
| * Clamp integer value between min and max bounds | |
| * @param {number} x - Value to clamp | |
| * @param {number} min - Minimum bound | |
| * @param {number} max - Maximum bound | |
| * @returns {number} Clamped value | |
| */ | |
| function clampInt(x, min, max) { | |
| x = x - ((x - max) & ((max - x) >> 31)); | |
| return x - ((x - min) & ((x - min) >> 31)); | |
| } | |
| /** | |
| * Fast average of two integers (avoids overflow) | |
| * @param {number} a - First integer | |
| * @param {number} b - Second integer | |
| * @returns {number} Average of a and b (rounded down) | |
| */ | |
| function avgInt(a, b) { | |
| return (a + b) >> 1; | |
| } | |
| /** | |
| * Safe average that handles potential overflow | |
| * @param {number} a - First integer | |
| * @param {number} b - Second integer | |
| * @returns {number} Average of a and b | |
| */ | |
| function avgIntSafe(a, b) { | |
| return (a & b) + ((a ^ b) >> 1); | |
| } | |
| // ============================================================================ | |
| // INCREMENT/DECREMENT OPERATIONS | |
| // ============================================================================ | |
| /** | |
| * Increment by 1 using bitwise operations (slower than ++) | |
| * Included for educational purposes | |
| * @param {number} n - Integer to increment | |
| * @returns {number} n + 1 | |
| */ | |
| function plusOneInt(n) { | |
| return -~n; | |
| } | |
| /** | |
| * Decrement by 1 using bitwise operations (slower than --) | |
| * Included for educational purposes | |
| * @param {number} n - Integer to decrement | |
| * @returns {number} n - 1 | |
| */ | |
| function minusOneInt(n) { | |
| return ~-n; | |
| } | |
| // ============================================================================ | |
| // POWER AND MODULO OPERATIONS | |
| // ============================================================================ | |
| /** | |
| * Fast power of 2 calculation: 2^n | |
| * @param {number} n - Exponent (0-30 for 32-bit safety) | |
| * @returns {number} 2^n | |
| */ | |
| function powOf2Int(n) { | |
| return 1 << n; | |
| } | |
| /** | |
| * Check if a number is a power of 2 | |
| * @param {number} value - Value to check | |
| * @returns {boolean} True if value is a power of 2 | |
| */ | |
| function isPowerOfTwo(value) { | |
| return value > 0 && (value & (value - 1)) === 0; | |
| } | |
| /** | |
| * Fast modulo for powers of 2 divisors only | |
| * Example: modulo(15, 8) === 15 % 8 === 7 | |
| * @param {number} numerator - Number to divide | |
| * @param {number} divisor - Must be a power of 2 | |
| * @returns {number} numerator % divisor | |
| */ | |
| function moduloPowerOf2(numerator, divisor) { | |
| if (!isPowerOfTwo(divisor)) { | |
| throw new Error('Divisor must be a power of 2'); | |
| } | |
| return numerator & (divisor - 1); | |
| } | |
| /** | |
| * Find the next higher power of 2 | |
| * @param {number} n - Input number | |
| * @returns {number} Next power of 2 >= n | |
| */ | |
| function nextPowerOf2(n) { | |
| if (n <= 1) return 1; | |
| n--; | |
| n |= n >> 1; | |
| n |= n >> 2; | |
| n |= n >> 4; | |
| n |= n >> 8; | |
| n |= n >> 16; | |
| return n + 1; | |
| } | |
| // ============================================================================ | |
| // BIT MANIPULATION OPERATIONS | |
| // ============================================================================ | |
| /** | |
| * Set a specific bit to 1 | |
| * @param {number} n - Original number | |
| * @param {number} bit - Bit position (0-31) | |
| * @returns {number} Number with bit set | |
| */ | |
| function setBit(n, bit) { | |
| return n | (1 << bit); | |
| } | |
| /** | |
| * Clear a specific bit (set to 0) | |
| * @param {number} n - Original number | |
| * @param {number} bit - Bit position (0-31) | |
| * @returns {number} Number with bit cleared | |
| */ | |
| function clearBit(n, bit) { | |
| return n & ~(1 << bit); | |
| } | |
| /** | |
| * Toggle a specific bit | |
| * @param {number} n - Original number | |
| * @param {number} bit - Bit position (0-31) | |
| * @returns {number} Number with bit toggled | |
| */ | |
| function toggleBit(n, bit) { | |
| return n ^ (1 << bit); | |
| } | |
| /** | |
| * Check if a specific bit is set | |
| * @param {number} n - Number to check | |
| * @param {number} bit - Bit position (0-31) | |
| * @returns {boolean} True if bit is set | |
| */ | |
| function isBitSet(n, bit) { | |
| return (n & (1 << bit)) !== 0; | |
| } | |
| /** | |
| * Count the number of set bits (population count) | |
| * @param {number} n - Number to count bits in | |
| * @returns {number} Number of set bits | |
| */ | |
| function popCount(n) { | |
| n = n - ((n >> 1) & 0x55555555); | |
| n = (n & 0x33333333) + ((n >> 2) & 0x33333333); | |
| return (((n + (n >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24; | |
| } | |
| /** | |
| * Find position of the lowest set bit (0-indexed) | |
| * @param {number} n - Number to analyze | |
| * @returns {number} Position of lowest set bit, or -1 if n is 0 | |
| */ | |
| function findLowestSetBit(n) { | |
| if (n === 0) return -1; | |
| return popCount((n & -n) - 1); | |
| } | |
| // ============================================================================ | |
| // UTILITY FUNCTIONS | |
| // ============================================================================ | |
| /** | |
| * Check if number is odd | |
| * @param {number} n - Number to check | |
| * @returns {boolean} True if odd | |
| */ | |
| function isOdd(n) { | |
| return (n & 1) === 1; | |
| } | |
| /** | |
| * Check if number is even | |
| * @param {number} n - Number to check | |
| * @returns {boolean} True if even | |
| */ | |
| function isEven(n) { | |
| return (n & 1) === 0; | |
| } | |
| /** | |
| * Check if two numbers have the same sign | |
| * @param {number} a - First number | |
| * @param {number} b - Second number | |
| * @returns {boolean} True if same sign | |
| */ | |
| function hasSameSign(a, b) { | |
| return (a ^ b) >= 0; | |
| } | |
| /** | |
| * Toggle between two values: if n === a return b, if n === b return a | |
| * @param {number} n - Current value | |
| * @param {number} a - First value | |
| * @param {number} b - Second value | |
| * @returns {number} Toggled value | |
| */ | |
| function toggleValue(n, a, b) { | |
| return a ^ b ^ n; | |
| } | |
| /** | |
| * Swap two elements in an array without temporary variable | |
| * Warning: This will fail if i === j or if array contains non-integers | |
| * @param {number[]} array - Array to modify | |
| * @param {number} i - First index | |
| * @param {number} j - Second index | |
| */ | |
| function swapArrayElements(array, i, j) { | |
| if (i === j) return; // Avoid zeroing out element | |
| array[i] ^= array[j]; | |
| array[j] ^= array[i]; | |
| array[i] ^= array[j]; | |
| } | |
| /** | |
| * Safe array swap that works with any values | |
| * @param {any[]} array - Array to modify | |
| * @param {number} i - First index | |
| * @param {number} j - Second index | |
| */ | |
| function swapArrayElementsSafe(array, i, j) { | |
| if (i !== j) { | |
| const temp = array[i]; | |
| array[i] = array[j]; | |
| array[j] = temp; | |
| } | |
| } | |
| // ============================================================================ | |
| // ADVANCED BIT MANIPULATION | |
| // ============================================================================ | |
| /** | |
| * Reverse the bits in a 32-bit integer | |
| * @param {number} n - Number to reverse bits | |
| * @returns {number} Number with bits reversed | |
| */ | |
| function reverseBits(n) { | |
| n = ((n >>> 1) & 0x55555555) | ((n & 0x55555555) << 1); | |
| n = ((n >>> 2) & 0x33333333) | ((n & 0x33333333) << 2); | |
| n = ((n >>> 4) & 0x0F0F0F0F) | ((n & 0x0F0F0F0F) << 4); | |
| n = ((n >>> 8) & 0x00FF00FF) | ((n & 0x00FF00FF) << 8); | |
| return (n >>> 16) | (n << 16); | |
| } | |
| /** | |
| * Find position of the highest set bit (0-indexed from right) | |
| * @param {number} n - Number to analyze | |
| * @returns {number} Position of highest set bit, or -1 if n is 0 | |
| */ | |
| function findHighestSetBit(n) { | |
| if (n === 0) return -1; | |
| let pos = 0; | |
| if (n >= 1 << 16) { n >>= 16; pos += 16; } | |
| if (n >= 1 << 8) { n >>= 8; pos += 8; } | |
| if (n >= 1 << 4) { n >>= 4; pos += 4; } | |
| if (n >= 1 << 2) { n >>= 2; pos += 2; } | |
| if (n >= 1 << 1) { pos += 1; } | |
| return pos; | |
| } | |
| /** | |
| * Get a specific bit value (0 or 1) | |
| * @param {number} n - Number to extract bit from | |
| * @param {number} bit - Bit position (0-31) | |
| * @returns {number} 0 or 1 | |
| */ | |
| function getBit(n, bit) { | |
| return (n >> bit) & 1; | |
| } | |
| /** | |
| * Extract a range of bits | |
| * @param {number} n - Source number | |
| * @param {number} start - Starting bit position | |
| * @param {number} length - Number of bits to extract | |
| * @returns {number} Extracted bits as number | |
| */ | |
| function extractBits(n, start, length) { | |
| const mask = (1 << length) - 1; | |
| return (n >> start) & mask; | |
| } | |
| /** | |
| * Set multiple bits using a mask | |
| * @param {number} n - Original number | |
| * @param {number} mask - Bit mask | |
| * @returns {number} Number with masked bits set | |
| */ | |
| function setBitMask(n, mask) { | |
| return n | mask; | |
| } | |
| /** | |
| * Clear multiple bits using a mask | |
| * @param {number} n - Original number | |
| * @param {number} mask - Bit mask | |
| * @returns {number} Number with masked bits cleared | |
| */ | |
| function clearBitMask(n, mask) { | |
| return n & ~mask; | |
| } | |
| /** | |
| * Check if all bits in mask are set | |
| * @param {number} n - Number to check | |
| * @param {number} mask - Bit mask to test | |
| * @returns {boolean} True if all masked bits are set | |
| */ | |
| function hasAllBits(n, mask) { | |
| return (n & mask) === mask; | |
| } | |
| /** | |
| * Check if any bits in mask are set | |
| * @param {number} n - Number to check | |
| * @param {number} mask - Bit mask to test | |
| * @returns {boolean} True if any masked bits are set | |
| */ | |
| function hasAnyBits(n, mask) { | |
| return (n & mask) !== 0; | |
| } | |
| // ============================================================================ | |
| // FAST DIVISION AND MULTIPLICATION | |
| // ============================================================================ | |
| /** | |
| * Fast division by 2^n (right shift) | |
| * @param {number} n - Number to divide | |
| * @param {number} pow - Power of 2 to divide by (shift amount) | |
| * @returns {number} n / (2^pow) | |
| */ | |
| function divideByPowerOf2(n, pow) { | |
| return n >> pow; | |
| } | |
| /** | |
| * Fast multiplication by 2^n (left shift) | |
| * @param {number} n - Number to multiply | |
| * @param {number} pow - Power of 2 to multiply by (shift amount) | |
| * @returns {number} n * (2^pow) | |
| */ | |
| function multiplyByPowerOf2(n, pow) { | |
| return n << pow; | |
| } | |
| /** | |
| * Fast multiplication by 3: n * 3 = n + (n << 1) | |
| * @param {number} n - Number to multiply by 3 | |
| * @returns {number} n * 3 | |
| */ | |
| function multiplyBy3(n) { | |
| return n + (n << 1); | |
| } | |
| /** | |
| * Fast multiplication by 5: n * 5 = n + (n << 2) | |
| * @param {number} n - Number to multiply by 5 | |
| * @returns {number} n * 5 | |
| */ | |
| function multiplyBy5(n) { | |
| return n + (n << 2); | |
| } | |
| /** | |
| * Fast multiplication by 7: n * 7 = n + (n << 1) + (n << 2) | |
| * @param {number} n - Number to multiply by 7 | |
| * @returns {number} n * 7 | |
| */ | |
| function multiplyBy7(n) { | |
| return n + (n << 1) + (n << 2); | |
| } | |
| // ============================================================================ | |
| // ROTATION OPERATIONS | |
| // ============================================================================ | |
| /** | |
| * Rotate bits left (circular shift) | |
| * @param {number} n - Number to rotate | |
| * @param {number} shift - Number of positions to rotate | |
| * @returns {number} Number with bits rotated left | |
| */ | |
| function rotateLeft(n, shift) { | |
| shift &= 31; // Keep shift in range 0-31 | |
| return (n << shift) | (n >>> (32 - shift)); | |
| } | |
| /** | |
| * Rotate bits right (circular shift) | |
| * @param {number} n - Number to rotate | |
| * @param {number} shift - Number of positions to rotate | |
| * @returns {number} Number with bits rotated right | |
| */ | |
| function rotateRight(n, shift) { | |
| shift &= 31; // Keep shift in range 0-31 | |
| return (n >>> shift) | (n << (32 - shift)); | |
| } | |
| // ============================================================================ | |
| // COLOR/GRAPHICS UTILITIES | |
| // ============================================================================ | |
| /** | |
| * Pack RGBA values (0-255) into a single 32-bit integer | |
| * @param {number} r - Red component (0-255) | |
| * @param {number} g - Green component (0-255) | |
| * @param {number} b - Blue component (0-255) | |
| * @param {number} a - Alpha component (0-255) | |
| * @returns {number} Packed color value | |
| */ | |
| function packRGBA(r, g, b, a = 255) { | |
| return (a << 24) | (r << 16) | (g << 8) | b; | |
| } | |
| /** | |
| * Unpack RGBA values from a 32-bit integer | |
| * @param {number} color - Packed color value | |
| * @returns {Object} Object with r, g, b, a properties | |
| */ | |
| function unpackRGBA(color) { | |
| return { | |
| r: (color >> 16) & 0xFF, | |
| g: (color >> 8) & 0xFF, | |
| b: color & 0xFF, | |
| a: (color >> 24) & 0xFF | |
| }; | |
| } | |
| /** | |
| * Swap RGB to BGR or vice versa | |
| * @param {number} color - Color in RGB format | |
| * @returns {number} Color in BGR format | |
| */ | |
| function swapRGB(color) { | |
| return ((color & 0xFF) << 16) | (color & 0xFF00) | ((color >> 16) & 0xFF); | |
| } | |
| // ============================================================================ | |
| // HASH AND CHECKSUM FUNCTIONS | |
| // ============================================================================ | |
| /** | |
| * Simple 32-bit hash function (FNV-1a variant) | |
| * @param {number} n - Number to hash | |
| * @returns {number} Hash value | |
| */ | |
| function simpleHash32(n) { | |
| n = (n ^ 61) ^ (n >>> 16); | |
| n = n + (n << 3); | |
| n = n ^ (n >>> 4); | |
| n = n * 0x27d4eb2d; | |
| n = n ^ (n >>> 15); | |
| return n >>> 0; // Ensure unsigned 32-bit | |
| } | |
| /** | |
| * XOR checksum of all bits | |
| * @param {number} n - Number to checksum | |
| * @returns {number} XOR of all bits (0 or 1) | |
| */ | |
| function xorChecksum(n) { | |
| n ^= n >>> 16; | |
| n ^= n >>> 8; | |
| n ^= n >>> 4; | |
| n ^= n >>> 2; | |
| n ^= n >>> 1; | |
| return n & 1; | |
| } | |
| // ============================================================================ | |
| // GRAY CODE OPERATIONS | |
| // ============================================================================ | |
| /** | |
| * Convert binary to Gray code | |
| * @param {number} binary - Binary number | |
| * @returns {number} Gray code representation | |
| */ | |
| function binaryToGray(binary) { | |
| return binary ^ (binary >>> 1); | |
| } | |
| /** | |
| * Convert Gray code to binary | |
| * @param {number} gray - Gray code number | |
| * @returns {number} Binary representation | |
| */ | |
| function grayToBinary(gray) { | |
| let binary = gray; | |
| while (gray >>>= 1) { | |
| binary ^= gray; | |
| } | |
| return binary; | |
| } | |
| // ============================================================================ | |
| // SPECIALIZED BIT PATTERNS | |
| // ============================================================================ | |
| /** | |
| * Turn off the rightmost 1-bit | |
| * Useful for iterating through set bits | |
| * @param {number} n - Input number | |
| * @returns {number} Number with rightmost 1-bit cleared | |
| */ | |
| function turnOffRightmost1Bit(n) { | |
| return n & (n - 1); | |
| } | |
| /** | |
| * Isolate the rightmost 1-bit (keep only the rightmost set bit) | |
| * @param {number} n - Input number | |
| * @returns {number} Only the rightmost 1-bit, all others cleared | |
| */ | |
| function isolateRightmost1Bit(n) { | |
| return n & (-n); | |
| } | |
| /** | |
| * Right propagate the rightmost 1-bit | |
| * Sets all bits to the right of the rightmost 1-bit | |
| * @param {number} n - Input number | |
| * @returns {number} Number with right-propagated rightmost 1-bit | |
| */ | |
| function rightPropagateRightmost1Bit(n) { | |
| return n | (n - 1); | |
| } | |
| /** | |
| * Isolate the rightmost 0-bit | |
| * @param {number} n - Input number | |
| * @returns {number} Only the rightmost 0-bit as a 1, all others cleared | |
| */ | |
| function isolateRightmost0Bit(n) { | |
| return ~n & (n + 1); | |
| } | |
| /** | |
| * Turn on the rightmost 0-bit | |
| * @param {number} n - Input number | |
| * @returns {number} Number with rightmost 0-bit set to 1 | |
| */ | |
| function turnOnRightmost0Bit(n) { | |
| return n | (n + 1); | |
| } | |
| /** | |
| * Check if all bits are the same (all 0s or all 1s in the relevant bits) | |
| * @param {number} n - Input number | |
| * @returns {boolean} True if all bits are the same | |
| */ | |
| function areAllBitsSame(n) { | |
| return (n & (n + 1)) === 0; | |
| } | |
| /** | |
| * Count trailing zeros (number of zeros from the right) | |
| * @param {number} n - Input number | |
| * @returns {number} Number of trailing zeros | |
| */ | |
| function countTrailingZeros(n) { | |
| if (n === 0) return 32; | |
| return popCount((n & -n) - 1); | |
| } | |
| /** | |
| * Alternative trailing zeros count using bit manipulation | |
| * @param {number} n - Input number | |
| * @returns {boolean} True if there are trailing unset bits after rightmost set bit | |
| */ | |
| function hasTrailingUnsetBits(n) { | |
| return !!(~n & (n - 1)); | |
| } | |
| // ============================================================================ | |
| // ENHANCED MATH OPERATIONS | |
| // ============================================================================ | |
| /** | |
| * Fast Math.floor for positive numbers using bitwise OR | |
| * @param {number} n - Number to floor | |
| * @returns {number} Floored value | |
| */ | |
| function fastFloor(n) { | |
| return n | 0; | |
| } | |
| /** | |
| * Bitwise max implementation | |
| * @param {number} x - First number | |
| * @param {number} y - Second number | |
| * @returns {number} Maximum value | |
| */ | |
| function bitwiseMax(x, y) { | |
| return x ^ ((x ^ y) & -(x < y)); | |
| } | |
| /** | |
| * Bitwise min implementation | |
| * @param {number} x - First number | |
| * @param {number} y - Second number | |
| * @returns {number} Minimum value | |
| */ | |
| function bitwiseMin(x, y) { | |
| return y ^ ((x ^ y) & -(x < y)); | |
| } | |
| /** | |
| * Check if two integers have opposite signs | |
| * @param {number} x - First integer | |
| * @param {number} y - Second integer | |
| * @returns {boolean} True if signs are opposite | |
| */ | |
| function haveOppositeSigns(x, y) { | |
| return (x ^ y) < 0; | |
| } | |
| /** | |
| * Merge bits from two values according to a mask | |
| * More efficient than (x & ~mask) | (y & mask) | |
| * @param {number} x - Source for unmasked bits | |
| * @param {number} y - Source for masked bits | |
| * @param {number} mask - Bit mask (1 = take from y, 0 = take from x) | |
| * @returns {number} Merged result | |
| */ | |
| function mergeBits(x, y, mask) { | |
| return x ^ ((x ^ y) & mask); | |
| } | |
| /** | |
| * Advanced modulus for powers of 2 using bit manipulation | |
| * More complex but handles edge cases better | |
| * @param {number} numerator - Number to divide | |
| * @param {number} powerOf2 - Power of 2 divisor | |
| * @returns {number} Modulus result | |
| */ | |
| function advancedModuloPowerOf2(numerator, powerOf2) { | |
| const d = powerOf2; | |
| let m = numerator; | |
| if (numerator <= d) return numerator; | |
| const s = Math.log2(d); | |
| for (m = numerator; numerator > d; numerator = m) { | |
| for (m = 0; numerator; numerator >>= s) { | |
| m += numerator & (d - 1); | |
| } | |
| } | |
| return (m === d) ? 0 : m; | |
| } | |
| // ============================================================================ | |
| // TYPE CHECKING UTILITIES | |
| // ============================================================================ | |
| /** | |
| * Check if value cannot be parsed to a number (using bitwise double tilde) | |
| * @param {any} value - Value to check | |
| * @returns {boolean} True if value cannot be converted to number | |
| */ | |
| function isNotNumber(value) { | |
| return ~~value === 0 && value !== 0 && value !== false; | |
| } | |
| /** | |
| * Alternative check using unsigned right shift | |
| * @param {any} value - Value to check | |
| * @returns {boolean} True if value cannot be converted to number | |
| */ | |
| function isNotNumberAlt(value) { | |
| return (value >>> 0) === 0 && value !== 0 && value !== false; | |
| } | |
| // ============================================================================ | |
| // COLOR UTILITIES (ENHANCED) | |
| // ============================================================================ | |
| /** | |
| * Convert RGB to hex format using bitwise operations | |
| * @param {number} r - Red component (0-255) | |
| * @param {number} g - Green component (0-255) | |
| * @param {number} b - Blue component (0-255) | |
| * @returns {string} Hex color string | |
| */ | |
| function rgbToHex(r, g, b) { | |
| return '#' + ((1 << 24) + (r << 16) + (g << 8) + b).toString(16).slice(1); | |
| } | |
| /** | |
| * Get the bitwise difference between two hex values | |
| * @param {number} a - First hex value | |
| * @param {number} b - Second hex value | |
| * @returns {number} Bitwise difference | |
| */ | |
| function hexDifference(a, b) { | |
| return ~a & b; | |
| } | |
| // ============================================================================ | |
| // BIT ANALYSIS UTILITIES | |
| // ============================================================================ | |
| /** | |
| * Create array of bits from a number | |
| * @param {number} num - Number to convert | |
| * @param {number} bitCount - Number of bits to include (default 8) | |
| * @returns {number[]} Array of bits (0s and 1s) | |
| */ | |
| function numberToBitArray(num, bitCount = 8) { | |
| const bits = []; | |
| let mask = 1 << (bitCount - 1); | |
| while (mask > 0) { | |
| bits.push((mask & num) ? 1 : 0); | |
| mask >>= 1; | |
| } | |
| return bits; | |
| } | |
| /** | |
| * Brian Kernighan's bit counting method | |
| * More efficient for sparse bit patterns | |
| * @param {number} n - Number to count bits in | |
| * @returns {number} Count of set bits | |
| */ | |
| function popCountKernighan(n) { | |
| let count = 0; | |
| while (n) { | |
| n &= n - 1; // Clear the least significant bit set | |
| count++; | |
| } | |
| return count; | |
| } | |
| /** | |
| * Alternative population count using bit manipulation tricks | |
| * @param {number} n - Number to count bits in | |
| * @returns {number} Count of set bits | |
| */ | |
| function popCountFast(n) { | |
| n = n - ((n >> 1) & 0x55555555); | |
| n = (n & 0x33333333) + ((n >> 2) & 0x33333333); | |
| return (((n + (n >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24; | |
| } | |
| // ============================================================================ | |
| // TOGGLE AND SWAP UTILITIES | |
| // ============================================================================ | |
| /** | |
| * Toggle switch implementation using XOR | |
| * Useful for boolean state management | |
| * @param {number} state - Current state (0 or 1) | |
| * @returns {number} Toggled state | |
| */ | |
| function toggleSwitch(state) { | |
| return state ^ 1; | |
| } | |
| /** | |
| * XOR-based variable swap without temporary variable | |
| * Warning: Only works with integers, and fails if variables reference same memory | |
| * @param {object} obj - Object containing the variables | |
| * @param {string} prop1 - First property name | |
| * @param {string} prop2 - Second property name | |
| */ | |
| function xorSwapProperties(obj, prop1, prop2) { | |
| if (prop1 !== prop2) { | |
| obj[prop1] ^= obj[prop2]; | |
| obj[prop2] ^= obj[prop1]; | |
| obj[prop1] ^= obj[prop2]; | |
| } | |
| } | |
| // ============================================================================ | |
| // ADVANCED MODULUS OPERATIONS | |
| // ============================================================================ | |
| /** | |
| * General modulus division without division operator | |
| * Works for any divisor (not just powers of 2) | |
| * @param {number} numerator - Number to divide | |
| * @param {number} divisor - Divisor | |
| * @returns {number} Modulus result | |
| */ | |
| function modulusWithoutDivision(numerator, divisor) { | |
| if (divisor <= 0) throw new Error('Divisor must be positive'); | |
| // Handle negative numerator | |
| const isNegative = numerator < 0; | |
| numerator = Math.abs(numerator); | |
| while (numerator >= divisor) { | |
| let shift = 0; | |
| let temp = divisor; | |
| // Find the largest power of 2 multiple of divisor that fits | |
| while ((temp << 1) <= numerator) { | |
| temp <<= 1; | |
| shift++; | |
| } | |
| numerator -= temp; | |
| } | |
| return isNegative ? (numerator === 0 ? 0 : divisor - numerator) : numerator; | |
| } | |
| /** | |
| * Modulus for Mersenne numbers (2^n - 1) using bit manipulation | |
| * Very efficient for specific divisors like 7, 15, 31, 63, etc. | |
| * @param {number} numerator - Number to divide | |
| * @param {number} mersennePower - Power n where divisor = 2^n - 1 | |
| * @returns {number} Modulus result | |
| */ | |
| function modulusMersenne(numerator, mersennePower) { | |
| const divisor = (1 << mersennePower) - 1; | |
| let result = numerator; | |
| while (result > divisor) { | |
| let temp = 0; | |
| while (result) { | |
| temp += result & divisor; | |
| result >>= mersennePower; | |
| } | |
| result = temp; | |
| } | |
| return result === divisor ? 0 : result; | |
| } | |
| // ============================================================================ | |
| // ENHANCED TYPE CHECKING | |
| // ============================================================================ | |
| /** | |
| * Check if value is effectively zero using double tilde | |
| * Handles various falsy values that convert to 0 | |
| * @param {any} value - Value to check | |
| * @returns {boolean} True if value converts to 0 | |
| */ | |
| function isEffectivelyZero(value) { | |
| return ~~value === 0; | |
| } | |
| /** | |
| * Convert any value to 0 or 1 using double tilde | |
| * @param {any} value - Value to convert | |
| * @returns {number} 0 or 1 | |
| */ | |
| function toBinaryInt(value) { | |
| return ~~!!value; | |
| } | |
| /** | |
| * Safe integer conversion that handles edge cases | |
| * @param {any} value - Value to convert | |
| * @returns {number} Integer value or 0 | |
| */ | |
| function safeIntConversion(value) { | |
| return ~~value; | |
| } | |
| // ============================================================================ | |
| // MATHEMATICAL SIGN OPERATIONS | |
| // ============================================================================ | |
| /** | |
| * Get the sign of a number (-1, 0, or 1) using bitwise operations | |
| * @param {number} n - Number to get sign of | |
| * @returns {number} -1 for negative, 0 for zero, 1 for positive | |
| */ | |
| function getSignBitwise(n) { | |
| return (n > 0) - (n < 0); | |
| } | |
| /** | |
| * Alternative sign function using bit manipulation | |
| * @param {number} n - Number to get sign of | |
| * @returns {number} -1 for negative, 0 for zero, 1 for positive | |
| */ | |
| function getSignAlt(n) { | |
| return (n >> 31) | ((-n) >>> 31); | |
| } | |
| /** | |
| * Copy sign from one number to another using bitwise operations | |
| * @param {number} magnitude - Number providing the magnitude | |
| * @param {number} sign - Number providing the sign | |
| * @returns {number} Magnitude with sign applied | |
| */ | |
| function copySign(magnitude, sign) { | |
| const signBit = sign >> 31; | |
| return (magnitude ^ signBit) - signBit; | |
| } | |
| // ============================================================================ | |
| // POWER OF 2 ENHANCED OPERATIONS | |
| // ============================================================================ | |
| /** | |
| * Check if number is power of 2 using the classic bit trick | |
| * More explicit version with additional validation | |
| * @param {number} n - Number to check | |
| * @returns {boolean} True if n is a power of 2 | |
| */ | |
| function isPowerOf2Classic(n) { | |
| return n > 0 && (n & (n - 1)) === 0; | |
| } | |
| /** | |
| * Round down to nearest power of 2 | |
| * @param {number} n - Input number | |
| * @returns {number} Largest power of 2 <= n | |
| */ | |
| function floorPowerOf2(n) { | |
| if (n <= 0) return 0; | |
| n |= n >> 1; | |
| n |= n >> 2; | |
| n |= n >> 4; | |
| n |= n >> 8; | |
| n |= n >> 16; | |
| return n - (n >> 1); | |
| } | |
| // ============================================================================ | |
| // BIT FIELD OPERATIONS | |
| // ============================================================================ | |
| /** | |
| * Set a range of bits to a specific value | |
| * @param {number} target - Target number | |
| * @param {number} value - Value to insert | |
| * @param {number} start - Starting bit position | |
| * @param {number} length - Number of bits | |
| * @returns {number} Modified number | |
| */ | |
| function setBitRange(target, value, start, length) { | |
| const mask = ((1 << length) - 1) << start; | |
| return (target & ~mask) | ((value << start) & mask); | |
| } | |
| /** | |
| * Insert bits from source into target at specified position | |
| * @param {number} target - Target number | |
| * @param {number} source - Source number | |
| * @param {number} position - Bit position to insert at | |
| * @param {number} length - Number of bits to insert | |
| * @returns {number} Modified target | |
| */ | |
| function insertBits(target, source, position, length) { | |
| const mask = (1 << length) - 1; | |
| const clearMask = ~(mask << position); | |
| const insertMask = (source & mask) << position; | |
| return (target & clearMask) | insertMask; | |
| } | |
| /** | |
| * Check if a number is within 32-bit signed integer range | |
| * @param {number} n - Number to validate | |
| * @returns {boolean} True if within range | |
| */ | |
| function isValidInt32(n) { | |
| return Number.isInteger(n) && n >= MIN_SIGNED_32_BIT_INT && n <= MAX_SIGNED_32_BIT_INT; | |
| } | |
| // ============================================================================ | |
| // SIGNED/UNSIGNED CONVERSION | |
| // ============================================================================ | |
| /** | |
| * Convert signed 32-bit integer to unsigned | |
| * @param {number} n - Signed integer | |
| * @returns {number} Unsigned integer (0 to 4294967295) | |
| */ | |
| function toUnsigned32(n) { | |
| return n >>> 0; | |
| } | |
| /** | |
| * Convert unsigned 32-bit integer to signed | |
| * @param {number} n - Unsigned integer | |
| * @returns {number} Signed integer (-2147483648 to 2147483647) | |
| */ | |
| function toSigned32(n) { | |
| return n | 0; | |
| } | |
| // ============================================================================ | |
| // FLOATING POINT BIT MANIPULATION | |
| // ============================================================================ | |
| /** | |
| * Fast inverse square root (Quake III algorithm adaptation) | |
| * Note: This is more of a historical curiosity in JavaScript | |
| * @param {number} n - Number to get inverse square root of | |
| * @returns {number} Approximate 1/sqrt(n) | |
| */ | |
| function fastInvSqrt(n) { | |
| const threehalfs = 1.5; | |
| const x2 = n * 0.5; | |
| // Convert to 32-bit representation | |
| const buffer = new ArrayBuffer(4); | |
| const f32 = new Float32Array(buffer); | |
| const i32 = new Int32Array(buffer); | |
| f32[0] = n; | |
| i32[0] = 0x5f3759df - (i32[0] >> 1); // Magic number | |
| let y = f32[0]; | |
| y = y * (threehalfs - (x2 * y * y)); // 1st iteration | |
| y = y * (threehalfs - (x2 * y * y)); // 2nd iteration (optional) | |
| return y; | |
| } | |
| // ============================================================================ | |
| // BIT INTERLEAVING (MORTON CODES) | |
| // ============================================================================ | |
| /** | |
| * Interleave bits of two 16-bit numbers (Morton encoding) | |
| * Useful for Z-order curves in 2D space | |
| * @param {number} x - First 16-bit number | |
| * @param {number} y - Second 16-bit number | |
| * @returns {number} 32-bit Morton code | |
| */ | |
| function interleaveBits(x, y) { | |
| x = (x | (x << 8)) & 0x00FF00FF; | |
| x = (x | (x << 4)) & 0x0F0F0F0F; | |
| x = (x | (x << 2)) & 0x33333333; | |
| x = (x | (x << 1)) & 0x55555555; | |
| y = (y | (y << 8)) & 0x00FF00FF; | |
| y = (y | (y << 4)) & 0x0F0F0F0F; | |
| y = (y | (y << 2)) & 0x33333333; | |
| y = (y | (y << 1)) & 0x55555555; | |
| return x | (y << 1); | |
| } | |
| /** | |
| * De-interleave bits to extract X coordinate from Morton code | |
| * @param {number} morton - Morton encoded value | |
| * @returns {number} X coordinate (16-bit) | |
| */ | |
| function deinterleaveX(morton) { | |
| let x = morton & 0x55555555; | |
| x = (x | (x >> 1)) & 0x33333333; | |
| x = (x | (x >> 2)) & 0x0F0F0F0F; | |
| x = (x | (x >> 4)) & 0x00FF00FF; | |
| x = (x | (x >> 8)) & 0x0000FFFF; | |
| return x; | |
| } | |
| /** | |
| * De-interleave bits to extract Y coordinate from Morton code | |
| * @param {number} morton - Morton encoded value | |
| * @returns {number} Y coordinate (16-bit) | |
| */ | |
| function deinterleaveY(morton) { | |
| let y = (morton >> 1) & 0x55555555; | |
| y = (y | (y >> 1)) & 0x33333333; | |
| y = (y | (y >> 2)) & 0x0F0F0F0F; | |
| y = (y | (y >> 4)) & 0x00FF00FF; | |
| y = (y | (y >> 8)) & 0x0000FFFF; | |
| return y; | |
| } | |
| // ============================================================================ | |
| // UTILITY CLASSES | |
| // ============================================================================ | |
| /** | |
| * Bit Vector class for managing large sets of boolean flags | |
| */ | |
| class BitVector { | |
| constructor(size = 32) { | |
| this.size = size; | |
| this.words = new Uint32Array(Math.ceil(size / 32)); | |
| } | |
| /** | |
| * Set bit at position to 1 | |
| * @param {number} pos - Bit position | |
| */ | |
| set(pos) { | |
| if (pos >= 0 && pos < this.size) { | |
| const wordIndex = Math.floor(pos / 32); | |
| const bitIndex = pos % 32; | |
| this.words[wordIndex] |= (1 << bitIndex); | |
| } | |
| } | |
| /** | |
| * Set bit at position to 0 | |
| * @param {number} pos - Bit position | |
| */ | |
| clear(pos) { | |
| if (pos >= 0 && pos < this.size) { | |
| const wordIndex = Math.floor(pos / 32); | |
| const bitIndex = pos % 32; | |
| this.words[wordIndex] &= ~(1 << bitIndex); | |
| } | |
| } | |
| /** | |
| * Get bit value at position | |
| * @param {number} pos - Bit position | |
| * @returns {boolean} True if bit is set | |
| */ | |
| get(pos) { | |
| if (pos >= 0 && pos < this.size) { | |
| const wordIndex = Math.floor(pos / 32); | |
| const bitIndex = pos % 32; | |
| return (this.words[wordIndex] & (1 << bitIndex)) !== 0; | |
| } | |
| return false; | |
| } | |
| /** | |
| * Toggle bit at position | |
| * @param {number} pos - Bit position | |
| */ | |
| toggle(pos) { | |
| if (pos >= 0 && pos < this.size) { | |
| const wordIndex = Math.floor(pos / 32); | |
| const bitIndex = pos % 32; | |
| this.words[wordIndex] ^= (1 << bitIndex); | |
| } | |
| } | |
| /** | |
| * Count total number of set bits | |
| * @returns {number} Count of set bits | |
| */ | |
| popCount() { | |
| let count = 0; | |
| for (let word of this.words) { | |
| count += popCount(word); | |
| } | |
| return count; | |
| } | |
| /** | |
| * Clear all bits | |
| */ | |
| clearAll() { | |
| this.words.fill(0); | |
| } | |
| /** | |
| * Set all bits | |
| */ | |
| setAll() { | |
| this.words.fill(0xFFFFFFFF); | |
| // Clear extra bits in last word if size is not multiple of 32 | |
| const extraBits = this.size % 32; | |
| if (extraBits > 0) { | |
| const lastWordIndex = this.words.length - 1; | |
| this.words[lastWordIndex] &= (1 << extraBits) - 1; | |
| } | |
| } | |
| } | |
| // ============================================================================ | |
| // EXPORTS | |
| // ============================================================================ | |
| // For ES6 modules, you would use: | |
| // export { absInt, maxInt, minInt, /* ... all functions ... */, BitVector }; | |
| // For CommonJS: | |
| if (typeof module !== 'undefined' && module.exports) { | |
| module.exports = { | |
| // Constants | |
| PI, HALF_PI, TWO_PI, RADIAN, | |
| MAX_SIGNED_32_BIT_INT, MIN_SIGNED_32_BIT_INT, | |
| // Basic arithmetic | |
| absInt, maxInt, minInt, clampInt, avgInt, avgIntSafe, | |
| // Increment/decrement | |
| plusOneInt, minusOneInt, | |
| // Power and modulo | |
| powOf2Int, isPowerOfTwo, moduloPowerOf2, nextPowerOf2, | |
| // Bit manipulation | |
| setBit, clearBit, toggleBit, isBitSet, getBit, extractBits, | |
| setBitMask, clearBitMask, hasAllBits, hasAnyBits, | |
| popCount, findLowestSetBit, findHighestSetBit, reverseBits, | |
| // Fast math operations | |
| divideByPowerOf2, multiplyByPowerOf2, multiplyBy3, multiplyBy5, multiplyBy7, | |
| // Rotation | |
| rotateLeft, rotateRight, | |
| // Color utilities | |
| packRGBA, unpackRGBA, swapRGB, | |
| // Hash functions | |
| simpleHash32, xorChecksum, | |
| // Gray code | |
| binaryToGray, grayToBinary, | |
| // Signed/unsigned conversion | |
| toUnsigned32, toSigned32, | |
| // Advanced algorithms | |
| fastInvSqrt, interleaveBits, deinterleaveX, deinterleaveY, | |
| // Specialized bit patterns | |
| turnOffRightmost1Bit, isolateRightmost1Bit, rightPropagateRightmost1Bit, | |
| isolateRightmost0Bit, turnOnRightmost0Bit, areAllBitsSame, | |
| countTrailingZeros, hasTrailingUnsetBits, | |
| // Enhanced math operations | |
| fastFloor, bitwiseMax, bitwiseMin, haveOppositeSigns, mergeBits, | |
| advancedModuloPowerOf2, | |
| // Type checking | |
| isNotNumber, isNotNumberAlt, | |
| // Enhanced color utilities | |
| rgbToHex, hexDifference, | |
| // Bit analysis | |
| numberToBitArray, popCountKernighan, popCountFast, | |
| // Advanced modulus operations | |
| modulusWithoutDivision, modulusMersenne, | |
| // Enhanced type checking | |
| isEffectivelyZero, toBinaryInt, safeIntConversion, | |
| // Mathematical sign operations | |
| getSignBitwise, getSignAlt, copySign, | |
| // Enhanced power of 2 operations | |
| isPowerOf2Classic, floorPowerOf2, | |
| // Bit field operations | |
| setBitRange, insertBits, | |
| // Validation | |
| isValidInt32, isValidBitPosition, isExactFloat32, | |
| // Classes | |
| BitVector | |
| }; | |
| } | |
| // For browser globals: | |
| if (typeof window !== 'undefined') { | |
| window.BitwiseUtils = { | |
| absInt, maxInt, minInt, clampInt, avgInt, avgIntSafe, | |
| plusOneInt, minusOneInt, | |
| powOf2Int, isPowerOfTwo, moduloPowerOf2, nextPowerOf2, | |
| setBit, clearBit, toggleBit, isBitSet, getBit, extractBits, | |
| setBitMask, clearBitMask, hasAllBits, hasAnyBits, | |
| popCount, findLowestSetBit, findHighestSetBit, reverseBits, | |
| turnOffRightmost1Bit, isolateRightmost1Bit, rightPropagateRightmost1Bit, | |
| isolateRightmost0Bit, turnOnRightmost0Bit, areAllBitsSame, | |
| countTrailingZeros, hasTrailingUnsetBits, | |
| fastFloor, bitwiseMax, bitwiseMin, haveOppositeSigns, mergeBits, | |
| advancedModuloPowerOf2, | |
| isNotNumber, isNotNumberAlt, | |
| rgbToHex, hexDifference, | |
| modulusWithoutDivision, modulusMersenne, | |
| isEffectivelyZero, toBinaryInt, safeIntConversion, | |
| getSignBitwise, getSignAlt, copySign, | |
| isPowerOf2Classic, floorPowerOf2, | |
| setBitRange, insertBits, | |
| toggleSwitch, xorSwapProperties, | |
| isOdd, isEven, hasSameSign, toggleValue, | |
| swapArrayElements, swapArrayElementsSafe, | |
| isValidInt32, isValidBitPosition, isExactFloat32, | |
| BitVector | |
| }; | |
| } |
Looks like MODULO_INT doesn't work as intended as
numerator & (divisor - 1) != numerator % divisor
Or did I misunderstand the function of MODULO_INT?
@AugLuk yeah, it could be better documented what the limitations are.
The divisor has to be a power of 2.
When it is, you get the same result as % always (even for huge floats, it's 0 :v) but the correct result until a divisor of 2**53 aka 0x20000000000000
MODULO_INT only works for divisors of power 2 e.g. 2,4,8,16, ...
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
May be var MIN_SIGNED_32_BIT_INT = ~MAX_SIGNED_32_BIT_INT + 1 ?