log2.js (3614B)
1 /** 2 * @license Apache-2.0 3 * 4 * Copyright (c) 2018 The Stdlib Authors. 5 * 6 * Licensed under the Apache License, Version 2.0 (the "License"); 7 * you may not use this file except in compliance with the License. 8 * You may obtain a copy of the License at 9 * 10 * http://www.apache.org/licenses/LICENSE-2.0 11 * 12 * Unless required by applicable law or agreed to in writing, software 13 * distributed under the License is distributed on an "AS IS" BASIS, 14 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 15 * See the License for the specific language governing permissions and 16 * limitations under the License. 17 */ 18 19 'use strict'; 20 21 // VARIABLES // 22 23 // 4294901760 => 0xFFFF0000 => 11111111111111110000000000000000 24 var B4 = 0xFFFF0000 >>> 0; // asm type annotation 25 26 // 65280 => 0xFF00 => 00000000000000001111111100000000 27 var B3 = 0xFF00 >>> 0; // asm type annotation 28 29 // 240 => 0xF0 => 00000000000000000000000011110000 30 var B2 = 0xF0 >>> 0; // asm type annotation 31 32 // 12 => 0xC => 00000000000000000000000000001100 33 var B1 = 0xC >>> 0; // asm type annotation 34 35 // 2 => 0x2 => 00000000000000000000000000000010 36 var B0 = 0x2 >>> 0; // asm type annotation 37 38 // 16 => 00000000000000000000000000010000 39 var S4 = 16 >>> 0; // asm type annotation 40 41 // 8 => 00000000000000000000000000001000 42 var S3 = 8 >>> 0; // asm type annotation 43 44 // 4 => 00000000000000000000000000000100 45 var S2 = 4 >>> 0; // asm type annotation 46 47 // 2 => 00000000000000000000000000000010 48 var S1 = 2 >>> 0; // asm type annotation 49 50 // 1 => 00000000000000000000000000000001 51 var S0 = 1 >>> 0; // asm type annotation 52 53 54 // MAIN // 55 56 /** 57 * Computes an integer binary logarithm (base two). 58 * 59 * ## Method 60 * 61 * 1. Note that the largest unsigned 32-bit integer is `4294967295`, which is `2^{32}-1`. Hence, the integer binary logarithm cannot exceed `31` (i.e., `16 + 8 + 4 + 2 + 1`), which corresponds to the bit sequence 62 * 63 * ```binarystring 64 * 00000000000000000000000000011111 65 * ``` 66 * 67 * 2. Initialize a return variable with the value zero. 68 * 69 * 3. If at least one of the first sixteen most significant bits of the input 32-bit integer `x` is turned on, we know that the power to which the number `2` must be raised to obtain `x` is at least `16` (i.e., `x > 65536`). Hence, activate the corresponding bit of the return variable. Mutate `x` by shifting sixteen bits to the right, discarding the bits shifted off. 70 * 71 * 4. Carry out the following steps with `B` in `[ 8, 4, 2, 1 ]`: 72 * 73 * - If at least one of the next `B` most significant bits of the current `x` is turned on, we know that the power to which the number `2` must be raised to obtain `x` has to be increased by `B`. 74 * - Activate the bit of the return variable that corresponds to `B`. 75 * - Mutate `x` by shifting `B` bits to the right, discarding the bits shifted off. 76 * 77 * 5. The final value of the return variable is the integer binary logarithm of `x`. 78 * 79 * 80 * @param {uinteger32} x - input value 81 * @returns {uinteger32} integer binary logarithm 82 * 83 * @example 84 * var v = log2( 4 >>> 0 ); 85 * // returns 2 86 * 87 * @example 88 * var v = log2( 8 >>> 0 ); 89 * // returns 3 90 * 91 * @example 92 * var v = log2( 9 >>> 0 ); 93 * // returns 3 94 */ 95 function log2( x ) { 96 var out = 0 >>> 0; // asm type annotation 97 var y = x >>> 0; // asm type annotation 98 99 // `x >= 65536`: 100 if ( y & B4 ) { 101 y >>>= S4; 102 out |= S4; 103 } 104 // `x >= 256`: 105 if ( y & B3 ) { 106 y >>>= S3; 107 out |= S3; 108 } 109 // `x >= 16`: 110 if ( y & B2 ) { 111 y >>>= S2; 112 out |= S2; 113 } 114 // `x >= 4`: 115 if ( y & B1 ) { 116 y >>>= S1; 117 out |= S1; 118 } 119 // `x >= 2`: 120 if ( y & B0 ) { 121 y >>>= S0; 122 out |= S0; 123 } 124 return out; 125 } 126 127 128 // EXPORTS // 129 130 module.exports = log2;