### Number of digits

Numbers
Integers
Algorithms

Find number of digits with an unrolled div loop.

Code
Diff
• ``````// Unrolled div loop
fn digits(mut n: u64) -> usize {
let mut l = 1;
loop {
if n < 10 {
return l;
}
if n < 100 {
return l + 1;
}
if n < 1000 {
return l + 2;
}
if n < 10000 {
return l + 3;
}
n /= 10000;
l += 4;
}
}``````
•  1 + ```// Unrolled div loop ``` 1 1 ```fn digits(mut n: u64) -> usize { ``` 2 − ``` let mut l = 1; ``` 3 − ``` while n >= 10 { ``` 4 − ``` n /= 10; ``` 5 − ``` l += 1; ``` 3 + ``` let mut l = 1; ``` 4 + ``` loop { ``` 5 + ``` if n < 10 { ``` 6 + ``` return l; ``` 6 6 ``` } ``` 7 − ``` l ``` 8 + ``` if n < 100 { ``` 9 + ``` return l + 1; ``` 10 + ``` } ``` 11 + ``` if n < 1000 { ``` 12 + ``` return l + 2; ``` 13 + ``` } ``` 14 + ``` if n < 10000 { ``` 15 + ``` return l + 3; ``` 16 + ``` } ``` 17 + ``` n /= 10000; ``` 18 + ``` l += 4; ``` 19 + ``` } ``` 8 8 ```} ```

### Number of digits

Numbers
Integers
Algorithms

Find number of digits using a unrolled binary search.

Code
Diff
• ``````// Powers of 109
static POW10: [u64; 20] = [
1,
10,
100,
1000,
10000,
100000,
1000000,
10000000,
100000000,
1000000000,
10000000000,
100000000000,
1000000000000,
10000000000000,
100000000000000,
1000000000000000,
10000000000000000,
100000000000000000,
1000000000000000000,
10000000000000000000,
];

// Unrolled binary search
fn digits(n: u64) -> usize {
if n < POW10[16] {
if n < POW10[8] {
if n < POW10[4] {
if n < POW10[2] {
if n < POW10[1] {
1
} else {
2
}
} else {
if n < POW10[3] {
3
} else {
4
}
}
} else {
if n < POW10[6] {
if n < POW10[5] {
5
} else {
6
}
} else {
if n < POW10[7] {
7
} else {
8
}
}
}
} else {
if n < POW10[12] {
if n < POW10[10] {
if n < POW10[9] {
9
} else {
10
}
} else {
if n < POW10[11] {
11
} else {
12
}
}
} else {
if n < POW10[14] {
if n < POW10[13] {
13
} else {
14
}
} else {
if n < POW10[15] {
15
} else {
16
}
}
}
}
} else {
if n < POW10[18] {
if n < POW10[17] {
17
} else {
18
}
} else {
if n < POW10[19] {
19
} else {
20
}
}
}
}``````
•  1 − ```fn digits(mut n: u64) -> usize { ``` 2 − ``` let mut l = 1; ``` 3 − ``` while n >= 10 { ``` 4 − ``` n /= 10; ``` 5 − ``` l += 1; ``` 1 + ```// Powers of 109 ``` 2 + ```static POW10: [u64; 20] = [ ``` 3 + ``` 1, ``` 4 + ``` 10, ``` 5 + ``` 100, ``` 6 + ``` 1000, ``` 7 + ``` 10000, ``` 8 + ``` 100000, ``` 9 + ``` 1000000, ``` 10 + ``` 10000000, ``` 11 + ``` 100000000, ``` 12 + ``` 1000000000, ``` 13 + ``` 10000000000, ``` 14 + ``` 100000000000, ``` 15 + ``` 1000000000000, ``` 16 + ``` 10000000000000, ``` 17 + ``` 100000000000000, ``` 18 + ``` 1000000000000000, ``` 19 + ``` 10000000000000000, ``` 20 + ``` 100000000000000000, ``` 21 + ``` 1000000000000000000, ``` 22 + ``` 10000000000000000000, ``` 23 + ```]; ``` 24 + 25 + ```// Unrolled binary search ``` 26 + ```fn digits(n: u64) -> usize { ``` 27 + ``` if n < POW10[16] { ``` 28 + ``` if n < POW10[8] { ``` 29 + ``` if n < POW10[4] { ``` 30 + ``` if n < POW10[2] { ``` 31 + ``` if n < POW10[1] { ``` 32 + ``` 1 ``` 33 + ``` } else { ``` 34 + ``` 2 ``` 35 + ``` } ``` 36 + ``` } else { ``` 37 + ``` if n < POW10[3] { ``` 38 + ``` 3 ``` 39 + ``` } else { ``` 40 + ``` 4 ``` 41 + ``` } ``` 42 + ``` } ``` 43 + ``` } else { ``` 44 + ``` if n < POW10[6] { ``` 45 + ``` if n < POW10[5] { ``` 46 + ``` 5 ``` 47 + ``` } else { ``` 48 + ``` 6 ``` 49 + ``` } ``` 50 + ``` } else { ``` 51 + ``` if n < POW10[7] { ``` 52 + ``` 7 ``` 53 + ``` } else { ``` 54 + ``` 8 ``` 55 + ``` } ``` 56 + ``` } ``` 57 + ``` } ``` 58 + ``` } else { ``` 59 + ``` if n < POW10[12] { ``` 60 + ``` if n < POW10[10] { ``` 61 + ``` if n < POW10[9] { ``` 62 + ``` 9 ``` 63 + ``` } else { ``` 64 + ``` 10 ``` 65 + ``` } ``` 66 + ``` } else { ``` 67 + ``` if n < POW10[11] { ``` 68 + ``` 11 ``` 69 + ``` } else { ``` 70 + ``` 12 ``` 71 + ``` } ``` 72 + ``` } ``` 73 + ``` } else { ``` 74 + ``` if n < POW10[14] { ``` 75 + ``` if n < POW10[13] { ``` 76 + ``` 13 ``` 77 + ``` } else { ``` 78 + ``` 14 ``` 79 + ``` } ``` 80 + ``` } else { ``` 81 + ``` if n < POW10[15] { ``` 82 + ``` 15 ``` 83 + ``` } else { ``` 84 + ``` 16 ``` 85 + ``` } ``` 86 + ``` } ``` 87 + ``` } ``` 6 6 ``` } ``` 7 − ``` l ``` 89 + ``` } else { ``` 90 + ``` if n < POW10[18] { ``` 91 + ``` if n < POW10[17] { ``` 92 + ``` 17 ``` 93 + ``` } else { ``` 94 + ``` 18 ``` 95 + ``` } ``` 96 + ``` } else { ``` 97 + ``` if n < POW10[19] { ``` 98 + ``` 19 ``` 99 + ``` } else { ``` 100 + ``` 20 ``` 101 + ``` } ``` 102 + ``` } ``` 103 + ``` } ``` 8 8 ```} ```

### Number of digits

Numbers
Integers
Algorithms

We know that "2^i <= n < 2^(i+1)",
Where i is the highest set bit of the n.
Use ctlz and lookup tables to resolve number of
didgits with a single if statment.

Code
Diff
• ``````
// Powers of 10
static POW10: [u64; 20] = [
1,
10,
100,
1000,
10000,
100000,
1000000,
10000000,
100000000,
1000000000,
10000000000,
100000000000,
1000000000000,
10000000000000,
100000000000000,
1000000000000000,
10000000000000000,
100000000000000000,
1000000000000000000,
10000000000000000000,
];

// Number of decimal digits of binary numbers (1 << i)
// where i is the index in this table.
static BIN_TO_DEC: [u8; 66] = [
1,  1,  1,  1,  1,  2,  2,  2,  3,  3,  3,  4,
4,  4,  4,  5,  5,  5,  6,  6,  6,  7,  7,  7,
7,  8,  8,  8,  9,  9,  9, 10, 10, 10, 10, 11,
11, 11, 12, 12, 12, 13, 13, 13, 13, 14, 14, 14,
15, 15, 15, 16, 16, 16, 16, 17, 17, 17, 18, 18,
18, 19, 19, 19, 19, 20,
];

fn digits(mut n: u64) -> usize {
// We know that "2^i <= n < 2^(i+1)",
// Where i is the highest set bit of the n.
// Use ctlz and lookup tables to resolve number of
// didgits with a single if statment.
let i = 64 - n.leading_zeros() as usize;
let l = BIN_TO_DEC[i];
let h = BIN_TO_DEC[i + 1];
if n >= POW10[(h - 1) as usize] {
h as usize
} else {
l as usize
}
}
``````
•  1 + 2 + ```// Powers of 10 ``` 3 + ```static POW10: [u64; 20] = [ ``` 4 + ``` 1, ``` 5 + ``` 10, ``` 6 + ``` 100, ``` 7 + ``` 1000, ``` 8 + ``` 10000, ``` 9 + ``` 100000, ``` 10 + ``` 1000000, ``` 11 + ``` 10000000, ``` 12 + ``` 100000000, ``` 13 + ``` 1000000000, ``` 14 + ``` 10000000000, ``` 15 + ``` 100000000000, ``` 16 + ``` 1000000000000, ``` 17 + ``` 10000000000000, ``` 18 + ``` 100000000000000, ``` 19 + ``` 1000000000000000, ``` 20 + ``` 10000000000000000, ``` 21 + ``` 100000000000000000, ``` 22 + ``` 1000000000000000000, ``` 23 + ``` 10000000000000000000, ``` 24 + ```]; ``` 25 + 26 + ```// Number of decimal digits of binary numbers (1 << i) ``` 27 + ```// where i is the index in this table. ``` 28 + ```static BIN_TO_DEC: [u8; 66] = [ ``` 29 + ``` 1, 1, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, ``` 30 + ``` 4, 4, 4, 5, 5, 5, 6, 6, 6, 7, 7, 7, ``` 31 + ``` 7, 8, 8, 8, 9, 9, 9, 10, 10, 10, 10, 11, ``` 32 + ``` 11, 11, 12, 12, 12, 13, 13, 13, 13, 14, 14, 14, ``` 33 + ``` 15, 15, 15, 16, 16, 16, 16, 17, 17, 17, 18, 18, ``` 34 + ``` 18, 19, 19, 19, 19, 20, ``` 35 + ```]; ``` 36 + 1 1 ```fn digits(mut n: u64) -> usize { ``` 2 − ``` let mut l = 1; ``` 3 − ``` while n >= 10 { ``` 4 − ``` n /= 10; ``` 5 − ``` l += 1; ``` 6 − ``` } ``` 7 − ``` l ``` 38 + ``` // We know that "2^i <= n < 2^(i+1)", ``` 39 + ``` // Where i is the highest set bit of the n. ``` 40 + ``` // Use ctlz and lookup tables to resolve number of ``` 41 + ``` // didgits with a single if statment. ``` 42 + ``` let i = 64 - n.leading_zeros() as usize; ``` 43 + ``` let l = BIN_TO_DEC[i]; ``` 44 + ``` let h = BIN_TO_DEC[i + 1]; ``` 45 + ``` if n >= POW10[(h - 1) as usize] { ``` 46 + ``` h as usize ``` 47 + ``` } else { ``` 48 + ``` l as usize ``` 49 + ``` } ``` 8 8 ```} ```

### Number of digits

Numbers
Integers
Algorithms

Find length formatting string in stack allocated buffer.

Code
Diff
• ``````use std::io::{Write, Cursor};

fn digits(mut n: u64) -> usize {
let mut b = [0u8; 20];
let mut c = Cursor::new(&mut b[..]);
write!(c, "{}", n).unwrap();
c.position() as usize
}``````
•  1 + ```use std::io::{Write, Cursor}; ``` 2 + 1 1 ```fn digits(mut n: u64) -> usize { ``` 2 − ``` let mut l = 1; ``` 3 − ``` while n >= 10 { ``` 4 − ``` n /= 10; ``` 5 − ``` l += 1; ``` 6 − ``` } ``` 7 − ``` l ``` 4 + ``` let mut b = [0u8; 20]; ``` 5 + ``` let mut c = Cursor::new(&mut b[..]); ``` 6 + ``` write!(c, "{}", n).unwrap(); ``` 7 + ``` c.position() as usize ``` 8 8 ```} ```

### Number of digits

Numbers
Integers
Algorithms

Determine number of decimal digits in an unsiged 64bit integer.

``````fn digits(mut n: u64) -> usize {
let mut l = 1;
while n >= 10 {
n /= 10;
l += 1;
}
l
}``````