[PROG CHALLENGE #024] Non-Corporate Edition

Write a function:

int solution(int N);

that, given a positive integer N, returns the length of its longest binary gap. The function should return 0 if N doesn't contain a binary gap.

For example, given N = 1041 the function should return 5, because N has binary representation 10000010001 and so its longest binary gap is of length 5. Given N = 32 the function should return 0, because N has binary representation '100000' and thus no binary gaps.

pub fn longest_gap(n: u32) -> u32 {
let mut l: u32 = 0;
let mut c: u32 = 0;
let mut n_: u32 = n;
while n_ > 0 && n_ % 2 == 0 {
n_ >>= 1;
}
while n_ > 0 {
if n_ % 2 == 1 {
l = std::cmp::max(l, c);
c = 0;
} else {
c += 1;
}
n_ >>= 1;
}
l
}

pub fn longest_gap_cheating(n: u32) -> u32 {
let s = format!("{:b}", n);
let m = s
.split('1')
.rev()
.skip(1)
.map(|x| x.chars().count() as u32)
.max();
match m {
Some(x) => x,
None => 0,
}
}

#[cfg(test)]
mod test {
use super::*;

#[test]
pub fn normal() {
assert_eq!(longest_gap(1041), 5);
assert_eq!(longest_gap(32), 0);
}

#[test]
pub fn cheating() {
assert_eq!(longest_gap_cheating(1041), 5);
assert_eq!(longest_gap_cheating(32), 0);
}

#[test]
pub fn check() {
const NUM_CPUS: u32 = 12;
const ITERS: u32 = 100_000_000;
let p = ITERS / NUM_CPUS;
let mut t = vec![];
for j in 0..NUM_CPUS {
t.push(std::thread::spawn(move || {
for i in j * p..(j + 1) * p {
assert_eq!(longest_gap(i), longest_gap_cheating(i));
}
}));
}
for child in t {
let _ = child.join();
}
}
}