Earn extra honor and gain new allies!
Honor is earned for each new codewarrior who joins.
Learn more
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
    
    11
    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;
    
    66
        }
    
    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+
      }
    
    88
    }
    
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+
          } 
    
    66
        }
    
    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+
      }
    
    88
    }
    
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+
    11
    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+
      }
    
    88
    }
    
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+
    11
    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
    
    88
    }
    
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
}