1// Copyright (C) 2023 The Android Open Source Project 2// 3// Licensed under the Apache License, Version 2.0 (the "License"); 4// you may not use this file except in compliance with the License. 5// You may obtain a copy of the License at 6// 7// http://www.apache.org/licenses/LICENSE-2.0 8// 9// Unless required by applicable law or agreed to in writing, software 10// distributed under the License is distributed on an "AS IS" BASIS, 11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12// See the License for the specific language governing permissions and 13// limitations under the License. 14 15export class BigintMath { 16 static INT64_MAX: bigint = 2n ** 63n - 1n; 17 static INT64_MIN: bigint = -(2n ** 63n); 18 19 // Returns the smallest integral power of 2 that is not smaller than n. 20 // If n is less than or equal to 0, returns 1. 21 static bitCeil(n: bigint): bigint { 22 let result = 1n; 23 while (result < n) { 24 result <<= 1n; 25 } 26 return result; 27 } 28 29 // Returns the largest integral power of 2 which is not greater than n. 30 // If n is less than or equal to 0, returns 1. 31 static bitFloor(n: bigint): bigint { 32 let result = 1n; 33 while (result << 1n <= n) { 34 result <<= 1n; 35 } 36 return result; 37 } 38 39 // Returns the largest integral value x where 2^x is not greater than n. 40 static log2(n: bigint): number { 41 let result = 1n; 42 let log2 = 0; 43 while (result << 1n <= n) { 44 result <<= 1n; 45 ++log2; 46 } 47 return log2; 48 } 49 50 // Returns the integral multiple of step which is closest to n. 51 // If step is less than or equal to 0, returns n. 52 static quant(n: bigint, step: bigint): bigint { 53 step = BigintMath.max(1n, step); 54 const halfStep = step / 2n; 55 return step * ((n + halfStep) / step); 56 } 57 58 // Returns the largest integral multiple of step which is not larger than n. 59 // If step is less than or equal to 0, returns n. 60 static quantFloor(n: bigint, step: bigint): bigint { 61 step = BigintMath.max(1n, step); 62 if (n >= 0) { 63 return n - (n % step); 64 } else { 65 // If we're negative, just subtract one more "step", unless we're already 66 // aligned to a step then do nothing. 67 return n - (n % step) - (n % step === 0n ? 0n : step); 68 } 69 } 70 71 // Returns the smallest integral multiple of step which is not smaller than n. 72 // If step is less than or equal to 0, returns n. 73 static quantCeil(n: bigint, step: bigint): bigint { 74 step = BigintMath.max(1n, step); 75 if (n >= 0) { 76 return n - (n % step) + (n % step === 0n ? 0n : step); 77 } else { 78 return n - (n % step); 79 } 80 } 81 82 // Returns the greater of a and b. 83 static max(a: bigint, b: bigint): bigint { 84 return a > b ? a : b; 85 } 86 87 // Returns the smaller of a and b. 88 static min(a: bigint, b: bigint): bigint { 89 return a < b ? a : b; 90 } 91 92 // Returns the number of 1 bits in n. 93 static popcount(n: bigint): number { 94 if (n < 0n) { 95 throw Error(`Can\'t get popcount of negative number ${n}`); 96 } 97 let count = 0; 98 while (n) { 99 if (n & 1n) { 100 ++count; 101 } 102 n >>= 1n; 103 } 104 return count; 105 } 106 107 // Return the ratio between two bigints as a number. 108 static ratio(dividend: bigint, divisor: bigint): number { 109 return Number(dividend) / Number(divisor); 110 } 111 112 // Calculates the absolute value of a n. 113 static abs(n: bigint) { 114 return n < 0n ? -1n * n : n; 115 } 116} 117