Implement `internal_bit`

[qryxip]

Closes #30.

[qryxip]

Seeing the usage of ceil_pow2 in the original ACL, I think the signature should be fn(u32) -> u32.

[TonalidadeHidrica]

LGTM. Since three noodles depends on this modules, I think this PR should be merged ASAP.

[qryxip]

$ cargo +nightly bench --bench bench
   Compiling a v0.1.0 (/home/ryo/src/local/hage/a)
    Finished bench [optimized] target(s) in 0.50s
     Running target/release/deps/bench-13a9f15c9072cc25

running 2 tests
test naive              ... bench:   2,115,928 ns/iter (+/- 117,993)
test with_leading_zeros ... bench:     104,699 ns/iter (+/- 8,538)

test result: ok. 0 passed; 0 failed; 0 ignored; 2 measured; 0 filtered out

[TonalidadeHidrica]

@qryxip Just for curiosity, could you tell me which two function you compared? The original one (while loop + comparison) and the Rust implementation (count leading zeros)?

[qryxip]

This. (I'm not used to bench)

#![feature(test)]

extern crate test;

use test::Bencher;

#[bench]
fn with_leading_zeros(bencher: &mut Bencher) {
    let values = values();
    bencher.iter(move || {
        values
            .iter()
            .map(|v| 32 - v.saturating_sub(1).leading_zeros())
            .fold(0, u32::wrapping_add)
    });
}

#[bench]
fn naive(bencher: &mut Bencher) {
    let values = values();
    bencher.iter(move || {
        values
            .iter()
            .map(|&v| {
                let mut x = 0;
                while (1 << x) < v {
                    x += 1;
                }
                x
            })
            .fold(0, u32::wrapping_add)
    });
}

fn values() -> Vec<u32> {
    std::fs::read_to_string("./values.txt")
        .unwrap()
        .split_ascii_whitespace()
        .map(|s| s.parse().unwrap())
        .collect()
}

import random
s = ''
for _ in range(100000):
    s += str(random.randint(0, 1 << 30))
    s += '\n'
with open('./values.txt', 'w') as file:
    file.write(s)

[qryxip]

$ cargo +nightly bench --bench bench
   Compiling a v0.1.0 (/home/ryo/src/local/hage/a)
    Finished bench [optimized] target(s) in 0.45s
     Running target/release/deps/bench-13a9f15c9072cc25

running 2 tests
test naive              ... bench:   2,144,545 ns/iter (+/- 99,698)
test with_leading_zeros ... bench:     144,275 ns/iter (+/- 11,680)

test result: ok. 0 passed; 0 failed; 0 ignored; 2 measured; 0 filtered out

#[bench]
fn with_leading_zeros(bencher: &mut Bencher) {
    #[inline(never)]
    fn run(v: u32) -> u32 {
        32 - v.saturating_sub(1).leading_zeros()
    }

    let values = values();
    bencher.iter(move || values.iter().copied().map(run).fold(0, u32::wrapping_add));
}

#[bench]
fn naive(bencher: &mut Bencher) {
    #[inline(never)]
    fn run(v: u32) -> u32 {
        let mut x = 0;
        while (1 << x) < v {
            x += 1;
        }
        x
    }

    let values = values();
    bencher.iter(move || values.iter().copied().map(run).fold(0, u32::wrapping_add));
}

[TonalidadeHidrica]

Can somebody merge this so that others can implement (lazy)segtree ?