-
Notifications
You must be signed in to change notification settings - Fork 1
/
is-bit-aligned.ts
52 lines (42 loc) · 1.51 KB
/
is-bit-aligned.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
import { getHighestSetBit, getLowestSetBit } from "./get-max-set-bit";
import { exponent } from "./exponent";
/**
* Returns true if the given number is bit-aligned in the sense that its a
* multiple of a given power of 2, say e, and such that the number, say a,
* conforms to: a/2^e < 2^(l-e), where l is the max allowed bit length.
* This essentially means the numbers act somewhat like fixed-point numbers
* which can drastically speed up some geometric algorithms and also reduce
* their complexity.
*
* Visually:
* These numbers (a,b and c) are grid aligned with e === 3 and max
* bitlength === 6:
* a -> 00|101100|000
* b -> 00|000100|000
* c -> 00|110111|000
* These are not
* a -> 01|101100|000
* b -> 00|000100|000
* These are not
* a -> 00|101100|000
* b -> 00|000100|100
* These are not
* a -> 00|101100|100
* b -> 00|000100|100
* @param as An array of numbers to check
* @param maxBitLength The max allowed bitlength
* @param gridSpacingExponent The grid spacing === 1^gridSpacingExponent
*/
function isBitAligned(
a: number,
maxBitLength: number,
gridSpacingExponent: number) {
if (a === 0) { return true; }
let e = exponent(a);
let maxSetBit = getHighestSetBit(a) - 52 + e;
let minSetBit = getLowestSetBit (a) - 52 + e;
let minBitBigEnough = minSetBit >= gridSpacingExponent;
let maxBitSmallEnough = maxSetBit <= maxBitLength-1 + gridSpacingExponent;
return minBitBigEnough && maxBitSmallEnough;
}
export { isBitAligned }