Logo

Programming-Idioms

This language bar is your friend. Select your favorite languages!
  • Scheme

Idiom #265 Even parity bit

Calculate the parity p of the integer variable i : 0 if it contains an even number of bits set, 1 if it contains an odd number of bits set.

(define (popcount x)
  (let loop ([s x]
             [count 0])
    (cond [(zero? s) count]
          [(odd? s) (loop (arithmetic-shift s -1) (add1 count))]
          [else (loop (arithmetic-shift s -1) count)])))

(define i 42)
(popcount i)

Named let is a common way to iterate in Scheme because it allows for tail recursion.
parity(Number) -> parity(Number, 0).

parity(Number, Count) when Number band 1 == 1 ->
        parity(Number bsr 1, Count + 1);
parity(Number, Count) when Number > 0 ->
        parity(Number bsr 1, Count);
parity(_, Count) ->
        Count rem 2.

New implementation...
< >
tkoenig