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 18 // Returns the smallest integral power of 2 that is not smaller than n. 19 // If n is less than or equal to 0, returns 1. 20 static bitCeil(n: bigint): bigint { 21 let result = 1n; 22 while (result < n) { 23 result <<= 1n; 24 } 25 return result; 26 }; 27 28 // Returns the largest integral power of 2 which is not greater than n. 29 // If n is less than or equal to 0, returns 1. 30 static bitFloor(n: bigint): bigint { 31 let result = 1n; 32 while ((result << 1n) <= n) { 33 result <<= 1n; 34 } 35 return result; 36 }; 37 38 // Returns the largest integral multiple of step which is not larger than n. 39 // If step is less than or equal to 0, returns n. 40 static quantizeFloor(n: bigint, step: bigint): bigint { 41 step = BigintMath.max(1n, step); 42 return step * (n / step); 43 } 44 45 // Return the integral multiple of step which is closest to n. 46 // If step is less than or equal to 0, returns n. 47 static quantize(n: bigint, step: bigint): bigint { 48 step = BigintMath.max(1n, step); 49 const halfStep = step / 2n; 50 return step * ((n + halfStep) / step); 51 } 52 53 // Return the greater of a and b 54 static max(a: bigint, b: bigint): bigint { 55 return a > b ? a : b; 56 } 57 58 // Return the smaller of a and b 59 static min(a: bigint, b: bigint): bigint { 60 return a < b ? a : b; 61 } 62 63 // Returns the number of 1 bits in n 64 static popcount(n: bigint): number { 65 if (n < 0n) { 66 throw Error(`Can\'t get popcount of negative number ${n}`); 67 } 68 let count = 0; 69 while (n) { 70 if (n & 1n) { 71 ++count; 72 } 73 n >>= 1n; 74 } 75 return count; 76 } 77} 78