Eliuds Eggs in Common-lisp: Complete Solution & Deep Dive Guide

Mastering Bit Counting in Common Lisp: The Complete Eliud's Eggs Guide

To count the number of set bits (1s) in a number's binary representation using Common Lisp, you can implement a recursive function without built-ins. This method involves repeatedly dividing the number by 2, adding the remainder (0 or 1) to an accumulator, and continuing until the number becomes zero.

You’ve stumbled upon a curious problem, a digital riddle left behind by an eccentric inventor. It’s a scenario straight out of the exclusive kodikra.com learning path: a high-tech chicken coop, a cryptic number on a display, and the simple question of "how many eggs are there?" You know the number is an encoded representation, and the key lies in its binary form. But there's a catch—you're tasked with solving it from first principles, without the convenient built-in functions that do the heavy lifting for you.

This feeling of being constrained is familiar to many developers. It's the challenge of peeling back the layers of abstraction to truly understand what's happening under the hood. You're not just trying to get the right answer; you're aiming for a deeper comprehension of binary arithmetic and algorithmic thinking. This guide promises to be your companion through that process. We will dissect the "Eliud's Eggs" problem, explore the elegant logic behind bit counting, and implement a robust solution in Common Lisp, solidifying your grasp of recursion, binary mechanics, and core programming concepts.

What is Bit Counting (Hamming Weight)?

At its core, the problem asks you to perform what is formally known in computer science and information theory as calculating the Hamming weight of a number. The Hamming weight, also known as population count (or `popcount`), is simply the number of non-zero symbols in a string of symbols. In our context, the "symbols" are the bits (binary digits) of an integer, so we are counting the number of 1s.

For example, the decimal number 21 is represented in binary as 10101. It has three '1's, so its Hamming weight is 3. If this were the number on Eliud's coop display, it would mean there are 3 eggs to collect.

This isn't just an academic puzzle. Counting set bits is a surprisingly practical operation with applications in various domains:

Cryptography: Many cryptographic algorithms rely on bitwise operations, and analyzing the bit patterns, including the number of set bits, is crucial.
Data Compression: Techniques like run-length encoding can use bit counts as part of their algorithms to find patterns in data.
Error Detection & Correction: Hamming distance, a related concept, measures the number of positions at which two strings of equal length are different. It's fundamental to creating error-correcting codes for reliable data transmission.
Database & Search Engines: Bitmap indexes use bitwise operations extensively to speed up queries. Counting bits is a common operation in this context to determine the size of result sets.

The restriction to avoid built-in functions like Common Lisp's logcount forces us to build the counting mechanism from scratch, which is an excellent way to internalize the underlying principles.

Why is Binary Representation the Key?

Computers don't think in decimal (base-10) as we do. Their native language is binary (base-2), a system composed entirely of 0s and 1s. Every integer you store in a computer is ultimately a sequence of these bits. To solve our problem, we must first understand how to translate a decimal number into this binary format, as the logic of our solution operates directly on the binary representation.

A base-2 system works with powers of 2. Let's break down the decimal number 21:

The binary representation 10101 can be read from right to left, where each position corresponds to a power of 2 (2⁰, 2¹, 2², 2³, etc.):


  1*(2^4) + 0*(2^3) + 1*(2^2) + 0*(2^1) + 1*(2^0)
= 1*16   + 0*8    + 1*4    + 0*2    + 1*1
= 16     + 0      + 4      + 0      + 1
= 21

The Division by Two Algorithm

So, how do we derive the binary string 10101 from the decimal number 21 algorithmically? The most common method is repeated division by 2. We repeatedly divide the number by 2 and record the remainder. The sequence of remainders, read in reverse, gives us the binary representation.

21 / 2 = 10 with a remainder of 1 (this is our least significant bit)
10 / 2 = 5 with a remainder of 0
5 / 2 = 2 with a remainder of 1
2 / 2 = 1 with a remainder of 0
1 / 2 = 0 with a remainder of 1 (this is our most significant bit)

Reading the remainders from bottom to top gives us 10101. Notice something crucial here: each remainder is either a 0 or a 1. This means that by calculating the remainder at each step, we are extracting one bit of the number at a time. If we simply add up these remainders, we get the total count of 1s! This insight is the foundation of our solution.

How to Solve It: The Recursive Approach in Common Lisp

With the division-by-two logic in hand, we can design our algorithm. We need a process that continues until the number becomes zero and keeps a running total of the remainders. This is a perfect use case for recursion.

A recursive function is one that calls itself. To avoid an infinite loop, it must have two key components:

Base Case: A condition that stops the recursion. In our case, this is when the number we are dividing becomes 0. At this point, we return the accumulated count.
Recursive Step: The part of the function that performs a piece of the work and then calls itself with a modified input, bringing it closer to the base case. Here, we will divide the number by 2 and call the function again with the quotient, adding the remainder to our running total.

Here is a visual representation of the recursive logic for the number 21:

    ● Start with number = 21, accumulator = 0
    │
    ▼
  ┌─────────────────────────────────┐
  │ Call do-egg-count(21, 0)        │
  └──────────────┬──────────────────┘
                 │ Is 21 == 0? No.
                 │ floor(21 / 2) ⟶ quotient=10, remainder=1
                 │
                 ▼
  ┌─────────────────────────────────┐
  │   Call do-egg-count(10, 0 + 1)  │
  └──────────────┬──────────────────┘
                 │ Is 10 == 0? No.
                 │ floor(10 / 2) ⟶ quotient=5, remainder=0
                 │
                 ▼
  ┌─────────────────────────────────┐
  │   Call do-egg-count(5, 1 + 0)   │
  └──────────────┬──────────────────┘
                 │ Is 5 == 0? No.
                 │ floor(5 / 2) ⟶ quotient=2, remainder=1
                 │
                 ▼
  ┌─────────────────────────────────┐
  │   Call do-egg-count(2, 1 + 1)   │
  └──────────────┬──────────────────┘
                 │ Is 2 == 0? No.
                 │ floor(2 / 2) ⟶ quotient=1, remainder=0
                 │
                 ▼
  ┌─────────────────────────────────┐
  │   Call do-egg-count(1, 2 + 0)   │
  └──────────────┬──────────────────┘
                 │ Is 1 == 0? No.
                 │ floor(1 / 2) ⟶ quotient=0, remainder=1
                 │
                 ▼
  ┌─────────────────────────────────┐
  │   Call do-egg-count(0, 2 + 1)   │
  └──────────────┬──────────────────┘
                 │ Is 0 == 0? Yes.
                 │
                 ▼
           Return accumulator: 3

This flow clearly illustrates how the problem is broken down into smaller, identical sub-problems until a simple base case is reached. The final answer is built up along the way in the accumulator.

Where to Implement It: A Deep Dive into the Common Lisp Code

Now, let's translate this logic into idiomatic Common Lisp code. The solution from the kodikra module is concise and effective, leveraging key features of the language.

The Solution Code


(defpackage :eliuds-eggs
  (:use :cl)
  (:export :egg-count))

(in-package :eliuds-eggs)

(defun do-egg-count (number &optional (acc 0))
  (if (= number 0)
      acc
      (multiple-value-bind (quot rem) (floor number 2)
        (do-egg-count quot (+ acc rem)))))

(defun egg-count (number)
  (do-egg-count number))

Line-by-Line Code Walkthrough

Let's dissect this code block by block to understand its structure and function.

1. Package Definition


(defpackage :eliuds-eggs
  (:use :cl)
  (:export :egg-count))

(defpackage :eliuds-eggs ...): This defines a new package named eliuds-eggs. In Common Lisp, packages are namespaces that prevent symbol name collisions. It's like a module or library in other languages.
(:use :cl): This line specifies that our new package should inherit all the standard symbols from the default :common-lisp package (aliased as :cl). This gives us access to functions like defun, if, +, etc., without needing to qualify them (e.g., cl:defun).
(:export :egg-count): This makes the symbol egg-count public. Any code outside this package can access this function. The helper function, do-egg-count, remains private to the package, which is excellent encapsulation.

2. Setting the Current Package


(in-package :eliuds-eggs)

This command switches the current working namespace to the one we just defined. All subsequent definitions (like our functions) will belong to the :eliuds-eggs package.

3. The Recursive Helper Function


(defun do-egg-count (number &optional (acc 0))
  (if (= number 0)
      acc
      (multiple-value-bind (quot rem) (floor number 2)
        (do-egg-count quot (+ acc rem)))))

(defun do-egg-count (number &optional (acc 0))): This defines our core recursive function.
- It takes a required argument, number.
- &optional (acc 0) defines an optional argument named acc (for accumulator) which defaults to 0 if not provided. This is a clean way to initialize our counter on the first call.
(if (= number 0) acc ...): This is our base case. If the number has been reduced to 0, the recursion stops, and the function returns the final value of the accumulator acc.
(multiple-value-bind (quot rem) (floor number 2) ...): This is the recursive step and a highlight of Common Lisp's power.
- The floor function in Common Lisp is special; it returns two values: the quotient and the remainder.
- multiple-value-bind is a macro that lets you capture these multiple return values and bind them to local variables. Here, the quotient is bound to quot and the remainder to rem.
(do-egg-count quot (+ acc rem)): This is the recursive call. We call the function again with the new quotient and an updated accumulator, which is the old accumulator plus the remainder (either 0 or 1).

4. The Public Wrapper Function


(defun egg-count (number)
  (do-egg-count number))

This is the public-facing API. It's a simple, clean function that takes just the number. It initiates the recursive process by calling our helper function do-egg-count. Because we didn't provide the optional acc argument, it automatically defaults to 0, kicking off the count correctly.

Running the Code

You can load and run this code in a Common Lisp REPL (Read-Eval-Print Loop), such as one provided by SBCL (Steel Bank Common Lisp).


$ sbcl
* (load "eliuds-eggs.lisp")
T
* (eliuds-eggs:egg-count 21)
3
* (eliuds-eggs:egg-count 0)
0
* (eliuds-eggs:egg-count 16)
1
; Binary 16 is 10000

An Alternative: The Iterative Approach

While recursion provides an elegant, mathematical solution, it's not the only way. For very large numbers, a deep recursion could potentially lead to a stack overflow error (though tail-call optimization in some Lisp implementations can mitigate this). An iterative solution using a loop avoids this risk by managing state explicitly rather than on the call stack.

Here’s how you could write an iterative version using Common Lisp's powerful loop macro.

Iterative Solution Code


(defun egg-count-iterative (number)
  (loop for n = number then (floor n 2)
        sum (rem n 2)
        while (> n 0)))

Dissecting the `loop` Macro

(loop ...): The start of the loop.
for n = number then (floor n 2): This sets up our loop variable n.
- On the first iteration, n is initialized to the input number.
- On every subsequent iteration (then), n is updated to be the result of (floor n 2). Note that we only care about the quotient here.
sum (rem n 2): This is the accumulator clause. In each iteration, it calculates the remainder of n divided by 2 ((rem n 2)) and adds it to an internal sum, which is returned at the end.
while (> n 0): This is the termination condition, equivalent to our recursive base case. The loop continues as long as n is greater than 0.

This iterative approach achieves the same result but with a different logical flow, which can be visualized as follows:

    ● Start with num = 21, total = 0
    │
    ▼
  ┌──────────────────┐
  │ Initialize Loop  │
  │ n = 21           │
  └────────┬─────────┘
           │
           ▼
    ◆ Is n > 0? (21 > 0) Yes.
   ╱           ╲
  Yes           No ⟶ Return total
  │
  ▼
┌───────────────────────────┐
│ total += rem(21, 2)  (1)  │
│ n = floor(21, 2)     (10) │
└────────────┬──────────────┘
             │
             └───────────> Back to Condition ◆

Pros and Cons: Recursion vs. Iteration

Choosing between these two approaches often depends on the problem, language, and performance requirements.

Aspect	Recursive Solution	Iterative Solution
Readability	Often closer to the mathematical definition of the problem. Can be very elegant.	Can be more straightforward for developers accustomed to imperative loops.
Performance	Function call overhead can make it slightly slower. Risk of stack overflow on very large inputs if not tail-call optimized.	Generally faster due to no function call overhead. No risk of stack overflow.
State Management	State (like the accumulator) is passed through function arguments. The call stack manages the flow implicitly.	State is managed explicitly with local variables inside the loop.
Idiomatic Lisp	Recursion is very natural and common in Lisp. Many implementations perform Tail Call Optimization (TCO), turning certain recursive calls into efficient jumps.	The `loop` macro is also highly idiomatic and extremely powerful for complex iterations.

For this specific problem from the kodikra module, both solutions are excellent. The recursive one is a beautiful demonstration of functional decomposition, while the iterative one showcases the power of the loop macro.

Frequently Asked Questions (FAQ)

1. What is "Hamming weight" and how does it relate to this problem?: Hamming weight (or population count) is the technical term for the number of '1's in a number's binary representation. The "Eliud's Eggs" problem is a creative framing of the task of calculating the Hamming weight of a given integer.
2. Why can't I just use the built-in `logcount` function in Common Lisp?: The purpose of this exercise in the kodikra learning path is to build the logic from scratch to understand the underlying algorithm. While (logcount n) would solve it instantly in a real-world application, doing so would bypass the learning objective of understanding binary arithmetic and recursive/iterative problem-solving.
3. Is recursion or iteration better for this problem?: For most practical inputs, both are perfectly fine. The recursive solution is often seen as more elegant and closer to the mathematical logic. The iterative solution is generally more performant and safer from stack overflow errors with extremely large numbers. In Common Lisp, if the recursion is in a "tail position," a good compiler can optimize it into an efficient loop anyway.
4. How does `multiple-value-bind` work in the recursive solution?: In Common Lisp, functions can return more than one value. The floor function returns two: the quotient and the remainder. multiple-value-bind is a macro that provides a clean syntax to capture each of these return values into separate variables (quot and rem in our case) for use within its body.
5. What happens if I input a negative number?: The behavior for negative numbers depends on the system's integer representation (usually two's complement). The provided division-based algorithm is designed for non-negative integers. Applying it to a negative number in Common Lisp's floor implementation would lead to an infinite loop, as dividing a negative number by 2 will always move away from zero (e.g., floor(-1/2) is -1).
6. Can this logic be applied to other programming languages?: Absolutely. The algorithm of repeatedly dividing by 2 and summing the remainders is language-agnostic. You can implement the same recursive or iterative logic in Python, Java, C++, JavaScript, or any other language using their respective division and modulo operators.
7. How can this be optimized for performance-critical applications?: For extreme performance, programmers often use bitwise operations instead of arithmetic. A classic optimization is the Kernighan's algorithm, which uses the expression n & (n - 1) to clear the least significant set bit in a loop. This loop runs exactly as many times as there are set bits, which is often faster than iterating through all bits.

Conclusion: More Than Just Counting Eggs

The "Eliud's Eggs" challenge, while presented as a simple story, serves as a gateway to fundamental computer science concepts. By solving it, you've not only written a Common Lisp function but have also delved into binary representation, algorithmic thinking, recursion, and iteration. You’ve learned how to break a problem down to its essential logic and implement it cleanly, respecting constraints that force a deeper understanding.

The skills honed here—manipulating numbers at the bit level and choosing the right algorithmic approach—are timeless. They are as relevant today in high-performance computing and data science as they were in the early days of programming. As you continue your journey, you'll find that this solid foundation makes more complex topics significantly easier to grasp.

Disclaimer: The code provided has been tested on Steel Bank Common Lisp (SBCL) version 2.4.x. As it uses standard Common Lisp features, it is expected to be fully compatible with other modern ANSI Common Lisp implementations.

Ready for the next challenge? Continue your journey in the Kodikra Common Lisp learning path or explore more fundamental concepts in our complete Common Lisp guide.

Published by Kodikra — Your trusted Common-lisp learning resource.

kodikra

Search this blog