4 files changed, 79 insertions, 2 deletions
diff --git a/challenge-079/xkr47/README b/challenge-079/xkr47/README
index 3a820dfa73..e4495cdc38 100644
--- a/challenge-079/xkr47/README
+++ b/challenge-079/xkr47/README
@@ -1,6 +1,6 @@
 Solution by Jonas Berlin.
 
-Install Rust from e.g. https://rustup.rs/ and run the rust solutions like follows:
+Install Rust from e.g. https://rustup.rs/ and run the Rust solutions like follows (replace ch-1 with ch-2 for second task):
 
 cd rust
-cargo run --release --bin ch-2 -- grid.txt words.txt
+cargo run --release --bin ch-1 -- [<arguments>]
diff --git a/challenge-079/xkr47/rust/Cargo.lock b/challenge-079/xkr47/rust/Cargo.lock
new file mode 100644
index 0000000000..acd40027c6
--- /dev/null
+++ b/challenge-079/xkr47/rust/Cargo.lock
@@ -0,0 +1,6 @@
+# This file is automatically @generated by Cargo.
+# It is not intended for manual editing.
+[[package]]
+name = "pwd-079"
+version = "0.1.0"
+
diff --git a/challenge-079/xkr47/rust/Cargo.toml b/challenge-079/xkr47/rust/Cargo.toml
new file mode 100644
index 0000000000..806c82037e
--- /dev/null
+++ b/challenge-079/xkr47/rust/Cargo.toml
@@ -0,0 +1,11 @@
+[package]
+name = "pwd-079"
+version = "0.1.0"
+authors = ["Jonas Berlin <xkr47@outerspace.dyndns.org>"]
+edition = "2018"
+
+[dependencies]
+
+[[bin]]
+name = "ch-1"
+path = "ch-1.rs"
diff --git a/challenge-079/xkr47/rust/ch-1.rs b/challenge-079/xkr47/rust/ch-1.rs
new file mode 100644
index 0000000000..786600c1fb
--- /dev/null
+++ b/challenge-079/xkr47/rust/ch-1.rs
@@ -0,0 +1,60 @@
+#![allow(dead_code)]
+
+use std::env;
+
+fn main() {
+    let n = env::args().skip(1).next().expect("Missing argument 'n'")
+        .parse().expect("Broken argument 'n' - expected number");
+
+    let total_count_set_bit = doit_optimized(n);
+
+    println!("{}", total_count_set_bit);
+}
+
+const N_BITS: u32 = 128;
+type NType = u128;
+
+fn doit_naive(n: NType) -> u32 {
+    let mut res: NType = 0;
+    for i in 1..=n {
+        res += i.count_ones() as NType;
+    }
+    (res % 1000000007) as u32
+}
+
+fn doit_optimized(mut n: NType) -> u32 {
+    n += 1; // convert to exclusive upper end
+    let mut res = 0;
+    let mut leading_bits = 0;
+    loop {
+        let highest_bit_plus_1 = N_BITS - n.leading_zeros();
+        if highest_bit_plus_1 < 1 {
+            break;
+        }
+        let mask = 1 << (highest_bit_plus_1 - 1);
+
+        res += mask * leading_bits + doit_pow2(mask);
+
+        // next iteration
+        n -= mask;
+        leading_bits += 1;
+    }
+    (res % 1000000007) as u32
+}
+
+// quickly calculate bits in 0..n-1 where n = 2^k
+fn doit_pow2(n: NType) -> NType {
+    (N_BITS - n.leading_zeros() - 1) as NType * n / 2
+}
+
+#[cfg(test)]
+mod tests {
+    use crate::{doit_naive, doit_optimized};
+
+    #[test]
+    fn identical_results_for_0_to_1000() {
+        for n in 1..1000 {
+            assert_eq!(doit_naive(n), doit_optimized(n), "for n={}", n);
+        }
+    }
+}