---

Clojure Bit Counting from Scratch: Master the Eliuds Eggs Algorithm

Counting the number of set bits (1s) in a number's binary form in Clojure, as taught in the Eliuds Eggs module, is achieved by repeatedly dividing the number by 2. The remainder of each division (either 0 or 1) is summed up until the original number becomes 0.

Have you ever inherited a piece of code or a system that felt like a puzzle box from a bygone era? You know the kind—brilliantly engineered, but with a logic that isn't immediately obvious. It works, but the *how* is a mystery you're tasked to unravel. This is a common rite of passage for developers, forcing us to look past high-level abstractions and dig into the fundamental principles of how data is actually represented.

This is precisely the scenario you'll encounter in the "Eliuds Eggs" module from the exclusive kodikra.com learning path. It’s not just about solving a problem; it's about adopting a mindset. You'll learn to deconstruct a number into its most basic components—its bits—and build a solution from the ground up, using the elegant, functional power of Clojure. This guide will walk you through every step of that process, turning a quirky problem into a profound learning experience.

---

What Exactly is the Eliuds Eggs Challenge?

At its heart, the Eliuds Eggs module presents a simple request with a crucial constraint. Your goal is to determine how many eggs need to be collected based on a single number. This number, however, is an encoded value where its binary representation holds the key. Each '1' in the number's binary form represents an egg to be collected.

So, if the digital display shows the number 89, you need to find its binary equivalent, which is 1011001, and then count the ones. In this case, there are four '1's, meaning Eliud needs to collect four eggs.

The core task is formally known in computer science as calculating the Hamming weight or the population count (popcount) of a number. It's the measure of the number of non-zero symbols in a string of symbols—in our case, the number of '1's in a binary string.

The Critical Restriction

The challenge comes with a significant rule: you are forbidden from using any built-in, standard library function that performs this task for you (like Java's Integer.bitCount()). This constraint is intentional. It forces you to move beyond simply calling a pre-built tool and instead construct the mechanism yourself. This is where true understanding is forged.

---

Why is Manual Bit Counting a Foundational Skill?

You might wonder, "If there's a built-in function for this, why bother learning to do it manually?" This is a valid question, and the answer lies in the difference between being a coder and being a computer scientist. Understanding the "how" behind the "what" provides several distinct advantages.

• Deepens Understanding of Data: At the lowest level, all data on a computer is just a series of bits. Learning to manipulate them directly gives you a profound appreciation for how numbers, characters, and complex data structures are stored and processed.
• Unlocks Performance Optimization: In high-performance computing, such as in graphics processing, cryptography, or network packet analysis, direct bit manipulation is often the key to squeezing out maximum efficiency. Operations on bits are incredibly fast.
• Prepares You for Technical Interviews: Bit manipulation problems are a staple of technical interviews at major tech companies. They are an excellent way for interviewers to gauge a candidate's grasp of computer science fundamentals and problem-solving skills.
• Builds Transferable Logic: The logic used to solve this problem—recursion, base cases, and accumulators—is a cornerstone of the functional programming paradigm, highly relevant not just in Clojure but across many modern languages.

---

How to Deconstruct the Number: The Binary Logic

Before we dive into the Clojure code, we must solidify our understanding of the mathematical logic. How can we inspect the bits of a number using only basic arithmetic? The answer lies in the properties of base-2 representation and integer division.

Consider the number 13. In binary, it is 1101. Our goal is to count the three '1's.

The key insight is this: the last bit of any binary number (the Least Significant Bit or LSB) tells you if the number is odd or even. If the LSB is 1, the number is odd. If it's 0, the number is even. We can get this value using the modulo operator (% 2).

• 13 % 2 = 1. We found our first '1'!

Now, how do we get to the next bit? We can use integer division by 2. Dividing a binary number by 2 is the equivalent of shifting all its bits one position to the right, effectively discarding the LSB we just checked.

• 13 / 2 = 6 (integer division). The binary representation of 6 is 110. Notice how 1101 has become 110.

We can now repeat the process on the new number, 6:

• 6 % 2 = 0. We found a '0'.
• 6 / 2 = 3. (Binary 11).

And again on 3:

• 3 % 2 = 1. We found our second '1'!
• 3 / 2 = 1. (Binary 1).

And again on 1:

• 1 % 2 = 1. We found our third '1'!
• 1 / 2 = 0.

Once our number becomes 0, there are no more bits to check, so we stop. By summing up the results of our modulo operations (1 + 0 + 1 + 1), we get the final count: 3. This simple, repeatable algorithm is the foundation of our Clojure solution.

Algorithm Logic Flow

Here is a visual representation of the algorithm we just described.

    ● Start with a number `N`
    │
    ▼
  ┌───────────────────┐
  │ Initialize count = 0 │
  └─────────┬─────────┘
            │
            ▼
    ◆ Is `N` > 0 ?
   ╱              ╲
 Yes (Loop)      No (End)
  │                 │
  │                 ▼
  │               ┌──────────────┐
  │               │ Return count │
  │               └──────────────┘
  │
  ├─ 1. Get remainder `R = N % 2`
  │
  ├─ 2. Add `R` to `count`
  │
  └─ 3. Update `N = N / 2` (integer division)
     │
     └───────────────────────────┐
                                 │
                                 ◄

---

The Clojure Solution: A Step-by-Step Code Walkthrough

Now, let's translate our algorithm into idiomatic Clojure. The language's functional nature and powerful features for recursion make it a perfect fit for this task. The solution provided in the kodikra.com module is concise, efficient, and beautifully expressive.

(ns eliuds-eggs)

(defn egg-count [number]
  (loop [value number
         acc 0]
    (if (= 0 value)
      acc
      (recur (quot value 2)
             (+ acc (rem value 2))))))

This small block of code is dense with powerful concepts. Let's break it down line by line.

1. Function Definition

(defn egg-count [number])

This is standard fare. We define a function named egg-count that accepts a single argument, number, which is the integer whose bits we want to count.

2. Introducing `loop` and `recur`

(loop [value number
       acc 0]
  ...)

This is the heart of our recursive process. In many languages, deep recursion can lead to a "stack overflow" error. Clojure provides the `loop`/`recur` construct for a special kind of recursion known as tail-call optimization (TCO). It allows the function to reuse the same stack frame for each iteration, effectively turning the recursion into a highly efficient loop under the hood. It gives us the declarative clarity of recursion with the performance of iteration.

• (loop [...] ...): This special form establishes a recursion point. It also initializes local bindings that will be updated in each "loop."
• value number: We create a local binding called value and initialize it with the input number. This will be the number we shrink in each step.
• acc 0: We create an accumulator binding called acc and initialize it to 0. This will hold our running total of '1' bits.

3. The Base Case: When to Stop

(if (= 0 value)
  acc
  ...)

Every recursive algorithm needs a "base case"—a condition that tells it when to stop. Without it, the loop would run forever. In our algorithm, we stop when the number we're processing becomes 0.

This code checks: "Is the current value equal to 0?" If it is, the process is complete, and we simply return the final accumulated value in acc.

4. The Recursive Step: The Workhorse

(recur (quot value 2)
       (+ acc (rem value 2)))

If the base case is not met (i.e., value is not 0), we execute the recursive step. The recur keyword is crucial; it tells Clojure to jump back to the nearest loop point with new values for the bindings.

Let's look at the new values we provide:

• The new `value` is `(quot value 2)`:
  • quot is Clojure's function for integer division. It's equivalent to our `number / 2` step in the manual walkthrough. It effectively performs the right bit-shift, preparing the number for the next iteration.
• The new `acc` is `(+ acc (rem value 2))`:
  • rem is Clojure's remainder function. (rem value 2) will return either 0 or 1, perfectly isolating the LSB.
  • We then add this result to our current accumulator, acc, updating the total count.

The recur call seamlessly passes these newly calculated values back to the top of the loop, and the process repeats until value finally becomes 0.

Visualizing the Execution Trace for `(egg-count 13)`

To make this concrete, let's trace the values of value and acc through each step of the loop for the input 13.

    ● Start: (egg-count 13)
    │
    ▼
  ┌──────────────────────────────────────────┐
  │ loop [value: 13, acc: 0]                 │
  └───────────┬──────────────────────────────┘
              │ Is value=0? No.
              ▼
  ┌──────────────────────────────────────────┐
  │ recur                                    │
  │ ├─ new value: (quot 13 2) → 6            │
  │ └─ new acc:   (+ 0 (rem 13 2)) → (+ 0 1) → 1 │
  └───────────┬──────────────────────────────┘
              │
              ▼
  ┌──────────────────────────────────────────┐
  │ loop [value: 6, acc: 1]                  │
  └───────────┬──────────────────────────────┘
              │ Is value=0? No.
              ▼
  ┌──────────────────────────────────────────┐
  │ recur                                    │
  │ ├─ new value: (quot 6 2) → 3             │
  │ └─ new acc:   (+ 1 (rem 6 2)) → (+ 1 0) → 1  │
  └───────────┬──────────────────────────────┘
              │
              ▼
  ┌──────────────────────────────────────────┐
  │ loop [value: 3, acc: 1]                  │
  └───────────┬──────────────────────────────┘
              │ Is value=0? No.
              ▼
  ┌──────────────────────────────────────────┐
  │ recur                                    │
  │ ├─ new value: (quot 3 2) → 1             │
  │ └─ new acc:   (+ 1 (rem 3 2)) → (+ 1 1) → 2  │
  └───────────┬──────────────────────────────┘
              │
              ▼
  ┌──────────────────────────────────────────┐
  │ loop [value: 1, acc: 2]                  │
  └───────────┬──────────────────────────────┘
              │ Is value=0? No.
              ▼
  ┌──────────────────────────────────────────┐
  │ recur                                    │
  │ ├─ new value: (quot 1 2) → 0             │
  │ └─ new acc:   (+ 2 (rem 1 2)) → (+ 2 1) → 3  │
  └───────────┬──────────────────────────────┘
              │
              ▼
  ┌──────────────────────────────────────────┐
  │ loop [value: 0, acc: 3]                  │
  └───────────┬──────────────────────────────┘
              │ Is value=0? Yes.
              ▼
    ● Return acc: 3

---

Alternative Approaches and Future-Proofing

While the recursive division method is clear and effective, it's worth knowing about other algorithms, especially one that leverages bitwise operations for potentially greater efficiency.

Kernighan's Algorithm

A clever and often faster method is Brian Kernighan's algorithm. The insight here is that subtracting 1 from a number flips the rightmost '1' bit to a '0' and all the '0' bits to its right to '1's.

For example, n = 12 (binary 1100). n - 1 = 11 (binary 1011).

If you then perform a bitwise AND operation (&) between n and n - 1, it has the effect of clearing the rightmost '1' bit.

1100 & 1011 = 1000

The number of times you can perform this operation before the number becomes 0 is exactly the number of '1' bits. The number of loops is equal to the number of set bits, not the total number of bits, which can be a significant improvement for sparse numbers (numbers with few '1's).

Here's how it could look in Clojure, using Java's bitwise operators via interop:

(defn egg-count-kernighan [number]
  (loop [value number
         count 0]
    (if (zero? value)
      count
      (recur (bit-and value (dec value))
             (inc count)))))

This is a fantastic alternative to have in your toolkit. It showcases a different way of thinking about the problem at the bit level.

Future-Proofing Your Knowledge

The principles of binary representation, bitwise operations, and algorithmic thinking are timeless. While Clojure might evolve and new languages will emerge, the fundamental logic you've learned in the Eliuds Eggs module will remain relevant. Understanding how to solve problems from first principles is a skill that transcends any single technology stack.

---

Pros and Cons of the Manual Approach

In a real-world production environment, you would almost certainly use the optimized, built-in function for counting bits. The purpose of this kodikra.com module is educational. Here's a clear comparison of the trade-offs.

Aspect	Manual Recursive Approach (Eliuds Eggs)	Built-in Standard Library Function
Performance	Good, but performance is tied to the total number of bits in the number (e.g., 64 loops for a 64-bit number).	Extremely fast. Often implemented using special CPU instructions (like POPCNT) that count bits in a single clock cycle.
Readability	Highly readable and expressive, especially in Clojure. The logic is explicit and easy to follow.	Very readable (e.g., (Integer/bitCount n)). It's a "black box" but the intent is clear.
Learning Value	Excellent. Forces you to understand binary arithmetic, recursion, and core language features.	Minimal. Teaches you how to call a function, but not how the underlying problem is solved.
Portability	The logic is universal and can be implemented in any programming language.	The function name and availability are specific to the language and its standard library.
Use Case	Learning environments, technical interviews, situations with constrained standard libraries.	Production code, performance-critical applications, any scenario where correctness and speed are prioritized over pedagogy.

---

Frequently Asked Questions (FAQ)

What is the purpose of `loop`/`recur` in Clojure?

loop/recur is Clojure's mechanism for creating efficient, stack-safe recursive loops. Standard function recursion can consume stack space for each call, potentially leading to a StackOverflowError. recur performs a tail-call optimization, which reuses the existing stack frame, making it as memory-efficient as a standard for or while loop in other languages.

Why not just use a built-in `bit-count` function?

The restriction in this specific kodikra.com module is purely for educational purposes. It's designed to ensure you understand the underlying algorithm and can build it from basic principles. In a real-world application, you should almost always prefer the highly optimized built-in function for performance and reliability.

What's the difference between `quot` and `/` in Clojure?

The / operator in Clojure can produce a rational number (a fraction) if the division is not whole. For example, (/ 13 2) results in 13/2. quot, on the other hand, is specifically for integer division; it returns the quotient and discards any remainder. (quot 13 2) results in 6, which is what our bit-shifting algorithm requires.

Is this recursive solution efficient?

Yes, thanks to tail-call optimization via loop/recur, it is very efficient in terms of memory. Its time complexity is O(log n) or, more accurately, O(k) where k is the number of bits in the number's representation (e.g., 32 or 64). It's efficient enough for most purposes, though not as fast as a hardware-level CPU instruction.

How does this relate to bitwise operators?

Our solution uses arithmetic operators (quot, rem) to achieve the same result as bitwise operators. (quot n 2) is equivalent to a right bit-shift (n >> 1). (rem n 2) is equivalent to a bitwise AND with 1 (n & 1). The Kernighan's algorithm alternative shown earlier uses bitwise operators (bit-and) directly.

Is Hamming weight used in real-world applications?

Absolutely. It's used in various fields. In cryptography, it's used to analyze the complexity of keys. In information theory, it's used in error detection and correction codes (like Hamming codes). In bioinformatics, it's used to measure the genetic distance between DNA strings.

How can I learn more about Clojure's fundamentals?

The best way to solidify your understanding is through practice. We highly recommend exploring the full Clojure language guide on kodikra.com, which covers everything from basic syntax to advanced concurrency concepts in a structured, hands-on way.

---

Conclusion: More Than Just Counting Eggs

The Eliuds Eggs challenge is a perfect example of a problem that is simple on the surface but rich with underlying computer science principles. By solving it, you've done more than just count bits; you've practiced core functional programming techniques, implemented a recursive algorithm efficiently using loop/recur, and gained a deeper, more tangible understanding of how numbers are represented in memory.

This foundational knowledge is invaluable. It's the bedrock upon which you can build more complex, performant, and elegant software. The logical thinking and problem-solving skills you've honed here will serve you well across your entire programming career, regardless of the language or framework you use.

Ready to apply these skills to new and exciting challenges? Explore the complete Clojure Learning Path on kodikra.com and continue your journey from foundational concepts to advanced application development.

Disclaimer: The code and concepts discussed in this article are based on modern versions of Clojure (1.10 and newer). While the core logic is timeless, always consult the official Clojure documentation for the most current syntax and library functions.

---

Published by Kodikra — Your trusted Clojure learning resource.