import Mathlib /-! # Number Of 1 Bits Given a positive integer n, write a function that returns the number of set bits in its binary representation (also known as the Hamming weight). ## Constraints - 1 <= n <= 2^31 - 1 ## Provided examples - `n = 11` → `3` - `n = 128` → `1` - `n = 2147483645` → `30` ## Synthesized negative examples - invalid input: `n = 0` ([structural] a predicate that admits 1 <= n <= 2^31 - 1. one below the stated minimum) - invalid input: `n = 4294967296` ([structural] a predicate that admits 1 <= n <= 2^31 - 1. 2^32, a power past the ceiling) - invalid input: `n = 2147483648` ([structural] a predicate that admits 1 <= n <= 2^31 - 1. one past the stated maximum) - `n = 11` → `4` is wrong ([structural] binary representation required but 'set' dropped. counts total bits of 1011 instead of set bits) - `n = 128` → `2` is wrong ([structural] applies the population count to n+1 rather than n. popcount(129) is 2, one more) - `n = 2147483645` → `29` is wrong ([structural] counts bits of n-1 rather than n. n-1 has 29 set bits) -/ namespace PNumberOf1Bits abbrev Input := Nat abbrev Output := Nat /-! ### Validity predicate (V) -/ /-- Valid input: a positive integer at most 2^31 - 1. -/ def isValidInput (input : Input) : Bool := 1 ≤ input && input ≤ 2 ^ 31 - 1 /-! ### Ideal specification (P_spec) -/ /-- `result` counts the set bits of `input`: some finite collection of bit positions has size `result` and holds a position exactly when that bit is 1. -/ def hammingWeight_spec (input : Input) (result : Output) : Prop := ∃ S : Finset ℕ, S.card = result ∧ ∀ i : ℕ, i ∈ S ↔ input.testBit i = true /-! ### Decidable specification (P_check) -/ /-- The unique finset of bit positions where `input` has a 1 bit. -/ def setBitsFinset (input : Input) : Finset ℕ := (Nat.bitIndices input).toFinset /-- Executable checker for `hammingWeight_spec` against the determined witness. -/ def hammingWeight_check (input : Input) (result : Output) : Bool := decide ((setBitsFinset input).card = result) /-- The candidate set the checker counts is exactly the one the specification describes. This is the whole of what has to be proved; the rest is bookkeeping. -/ theorem mem_bridge {input : Input} {i : ℕ} : i ∈ setBitsFinset input ↔ input.testBit i = true := by simp [setBitsFinset, List.mem_toFinset] /-- On valid input the checker accepts exactly the specified outputs. -/ theorem hammingWeight_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : hammingWeight_check input result ↔ hammingWeight_spec input result := by unfold hammingWeight_check hammingWeight_spec simp only [decide_eq_true_eq] constructor · intro hcard exact ⟨setBitsFinset input, by first | exact hcard | exact hcard.symm, fun i => mem_bridge⟩ · rintro ⟨s, hcard, hmem⟩ have hs : s = setBitsFinset input := by ext i rw [hmem i, mem_bridge] rw [hs] at hcard first | exact hcard | exact hcard.symm /-! ### Main algorithm (impl) -/ /-- Hamming weight as the cardinality of the checker's set-bit position finset. -/ def countSetBits (input : Input) : Output := (setBitsFinset input).card /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem countSetBits_correct (input : Input) (h : isValidInput input) : hammingWeight_spec input (countSetBits input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput 11 #guard isValidInput 128 #guard isValidInput 2147483645 /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput 0) #guard !(isValidInput 4294967296) #guard !(isValidInput 2147483648) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard hammingWeight_check 11 3 #guard hammingWeight_check 128 1 #guard hammingWeight_check 2147483645 30 /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(hammingWeight_check 11 4) #guard !(hammingWeight_check 128 2) #guard !(hammingWeight_check 2147483645 29) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard countSetBits 11 == 3 #guard countSetBits 128 == 1 #guard countSetBits 2147483645 == 30 /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard hammingWeight_check 11 (countSetBits 11) #guard hammingWeight_check 128 (countSetBits 128) #guard hammingWeight_check 2147483645 (countSetBits 2147483645) end PNumberOf1Bits