---

The Complete Guide to Solving Allergies with Bitmasking in Common Lisp

Unlocking complex data from a single number is a cornerstone of efficient programming. This guide explains how to decode an allergy score in Common Lisp using bitmasking, a powerful technique that uses bitwise operations to manage multiple boolean states within one integer, making your code faster and more memory-efficient.

Have you ever stared at a problem that required tracking dozens of simple yes/no states? Maybe it was user permissions, configuration flags, or product features. The naive approach—a list of booleans or a hash table—works, but it feels clumsy and inefficient. What if there was a way to pack all that information into a single, compact number? A method so elegant and fast it feels like a magic trick?

This is the exact challenge presented in the "Allergies" problem from the exclusive kodikra.com curriculum. You're given a single number, a person's "allergy score," and you must determine their complete list of allergies from it. This isn't just an academic puzzle; it's a gateway to understanding bitmasking, a fundamental technique used in high-performance systems, from operating system kernels to game engines. In this deep dive, we'll unravel this problem using the timeless power of Common Lisp.

---

What is the Allergy Scoring Problem?

The premise is simple yet profound. An allergy test returns a single integer score. This score is a composite value that encodes every allergy a person has from a predefined list. Each potential allergen is assigned a unique numerical value that is a power of two.

Here is the standard list of allergens and their associated values:

• eggs: 1 (which is 2⁰)
• peanuts: 2 (which is 2¹)
• shellfish: 4 (which is 2²)
• strawberries: 8 (which is 2³)
• tomatoes: 16 (which is 2⁴)
• chocolate: 32 (which is 2⁵)
• pollen: 64 (which is 2⁶)
• cats: 128 (which is 2⁷)

The total score is simply the sum of the values for each allergy the person has. For example:

• If a person is only allergic to peanuts (value 2) and strawberries (value 8), their score would be 2 + 8 = 10.
• If a person is allergic to cats (128), chocolate (32), and eggs (1), their score would be 128 + 32 + 1 = 161.

Our task is to build a system in Common Lisp that can take any score and perform two key operations:

1. Determine if a person is allergic to a specific item (e.g., given a score of 10, are they allergic to peanuts?).
2. Generate a complete list of all their allergies (e.g., given a score of 10, return a list containing "peanuts" and "strawberries").

The secret to solving this efficiently lies not in complex arithmetic, but in looking at these numbers in the language computers understand best: binary.

---

Why Use Bitmasking for This Problem?

At its heart, this problem is a perfect showcase for bitmasking. Bitmasking is a technique that uses bitwise operations to manipulate and query specific bits within an integer. When each allergen is assigned a value that is a power of two, it corresponds to a single, unique bit being set to '1' in its binary representation.

Let's visualize the allergen values in binary:

| Allergen      | Decimal | Binary      | Bit Position |
|---------------|---------|-------------|--------------|
| eggs          | 1       | 0000 0001   | 0            |
| peanuts       | 2       | 0000 0010   | 1            |
| shellfish     | 4       | 0000 0100   | 2            |
| strawberries  | 8       | 0000 1000   | 3            |
| tomatoes      | 16      | 0001 0000   | 4            |
| chocolate     | 32      | 0010 0000   | 5            |
| pollen        | 64      | 0100 0000   | 6            |
| cats          | 128     | 1000 0000   | 7            |

Notice how each allergen value has exactly one '1' bit, and it's in a different position. When we sum the values to get a total score, we are effectively performing a bitwise OR operation. A score of 10 (peanuts + strawberries) is 2 + 8. In binary, this is:

  0000 0010  (2 - peanuts)
+ 0000 1000  (8 - strawberries)
-----------
  0000 1010  (10 - the final score)

The resulting binary number 1010 acts as a set of flags. The bit at position 1 is 'on', and the bit at position 3 is 'on'. Every 'on' bit corresponds to a specific allergy. This is the core principle of bitmasking. We use a single integer (the "mask") to store multiple true/false states.

The Key Operation: Bitwise AND

To check for a specific allergy, we use the bitwise AND operation. In Common Lisp, the primary function for this is logand. When we perform a bitwise AND between the person's score and a specific allergen's value, we isolate the bit for that allergen.

For example, to check if a person with a score of 10 is allergic to peanuts (value 2):

  1010  (Score: 10)
& 0010  (Mask: 2 for peanuts)
------
  0010  (Result: 2)

The result is non-zero (it's 2). This tells us that the "peanuts" bit was set in the original score. If we check for an allergy they don't have, like shellfish (value 4):

  1010  (Score: 10)
& 0100  (Mask: 4 for shellfish)
------
  0000  (Result: 0)

The result is zero, confirming they are not allergic to shellfish. This simple, incredibly fast operation is the foundation of our solution.

---

How to Implement the Solution in Common Lisp

Now, let's translate this theory into a functional Common Lisp program. We'll structure our code logically, defining our data and then building the functions that operate on it.

Step 1: Defining the Allergens Data Structure

First, we need a way to store the mapping between allergen names and their bitmask values. A global constant holding an association list (alist) is a perfect, idiomatic choice in Lisp. An alist is a list of cons cells, where the car is the key and the cdr is the value.

(defpackage #:allergies
  (:use #:cl)
  (:export #:allergic-to-p #:list-allergies))

(in-package #:allergies)

;; Define the list of allergens and their corresponding bit values.
;; An association list is a good choice for this mapping.
(defconstant +allergen-list+
  '(("eggs"         . 1)
    ("peanuts"      . 2)
    ("shellfish"    . 4)
    ("strawberries" . 8)
    ("tomatoes"     . 16)
    ("chocolate"    . 32)
    ("pollen"       . 64)
    ("cats"         . 128))
  "An association list mapping allergen names to their bitmask values.")

We use defconstant to define +allergen-list+. The `+` symbols around the name are a common Lisp convention for naming global constants (known as "earmuffs"). We also include a docstring to explain its purpose.

Step 2: Checking for a Specific Allergy (`allergic-to-p`)

Our first function needs to answer the question: "Given a score and an allergen name, is the person allergic?" This function will look up the allergen's value and then use a bitwise test.

Common Lisp provides the function logtest, which is perfect for this. (logtest integer1 integer2) returns true if the bitwise AND of its arguments is not zero. It's more direct than using logand and then checking if the result is greater than zero.

(defun allergic-to-p (score allergen)
  "Checks if a given score indicates an allergy to a specific allergen.
   SCORE is the integer allergy score.
   ALLERGEN is the string name of the allergen to check."
  (let ((allergen-value (cdr (assoc allergen +allergen-list+ :test #'string=))))
    (when allergen-value
      (logtest score allergen-value))))

Code Walkthrough: `allergic-to-p`

1. `defun allergic-to-p (score allergen)`: We define a function named allergic-to-p that accepts two arguments: the numeric score and the string allergen. The -p suffix is a Lisp convention for predicate functions (functions that return a boolean-like value, true or false/nil).
2. `let ((allergen-value ...))`: We use a let block to create a local variable, allergen-value.
3. `(assoc allergen +allergen-list+ :test #'string=)`: This is the lookup. assoc searches the +allergen-list+ for a pair whose `car` (the key) matches the `allergen` string. We must specify :test #'string= because the default test is eql, which would not work for comparing strings. If found, it returns the entire pair, e.g., ("peanuts" . 2). If not found, it returns NIL.
4. `(cdr ...)`: We take the cdr of the result from assoc to extract the value (the number). If `assoc` returned NIL, `(cdr nil)` is also NIL.
5. `(when allergen-value ...)`: This is a safety check. If the provided allergen string was not found in our list, allergen-value will be NIL. The when block ensures we only proceed if we found a valid allergen.
6. `(logtest score allergen-value)`: This is the core logic. It performs the bitwise test. If the bit corresponding to allergen-value is set in score, it returns T (true); otherwise, it returns NIL (false).

Here is a visual representation of the logic inside allergic-to-p:

    ● Start: allergic-to-p(score, allergen)
    │
    ▼
  ┌─────────────────────────────┐
  │ Look up allergen in list    │
  │ e.g., "peanuts" → 2         │
  └─────────────┬───────────────┘
                │
                ▼
           ◆ Allergen Found?
          ╱               ╲
    Yes  │                 │ No
         ▼                 ▼
  ┌──────────────────┐   ┌──────────────────┐
  │ Perform bit test:│   │ Return NIL       │
  │ (logtest score 2)│   │ (false)          │
  └─────────┬────────┘   └─────────┬────────┘
            │                      │
            ▼                      ▼
       ◆ Result > 0?          ● End
      ╱             ╲
Yes  │               │ No
     ▼               ▼
┌───────────┐   ┌────────────┐
│ Return T  │   │ Return NIL │
│ (true)    │   │ (false)    │
└───────────┘   └────────────┘
     │               │
     └───────┬───────┘
             ▼
            ● End

Step 3: Listing All Allergies (`list-allergies`)

The second function must take a score and return a list of all corresponding allergen strings. The strategy is to iterate through our known allergens and use the allergic-to-p function we just built to check each one.

(defun list-allergies (score)
  "Returns a list of all allergens for a given score.
   SCORE is the integer allergy score.
   Allergens not in the known list are ignored."
  (loop for (name . value) in +allergen-list+
        when (logtest score value)
        collect name))

Code Walkthrough: `list-allergies`

This implementation uses the powerful loop macro, which provides a highly readable, almost English-like syntax for iteration.

1. `defun list-allergies (score)`: Defines the function that takes the numeric score.
2. `loop for (name . value) in +allergen-list+`: This is the heart of the iteration.
   • loop: Initializes the loop macro.
   • for (name . value) in +allergen-list+: This is a destructuring binding. For each element in +allergen-list+ (e.g., ("peanuts" . 2)), it automatically binds the `car` to a local variable name and the `cdr` to a local variable value.
3. `when (logtest score value)`: For each allergen, this is the conditional clause. It checks if the person is allergic to the current item using logtest, just like in our previous function.
4. `collect name`: If the when condition is true, the collect clause adds the value of name (the allergen string) to a list that the loop macro is implicitly building.

When the loop finishes iterating through all the allergens, it automatically returns the collected list. This approach is concise, declarative, and highly idiomatic in modern Common Lisp.

Here is a flowchart for the list-allergies function:

      ● Start: list-allergies(score)
      │
      ▼
┌───────────────────┐
│ Initialize empty  │
│ result_list       │
└─────────┬─────────┘
          │
          ▼
┌──────────────────────────────┐
│ Loop through each allergen   │
│ in `+allergen-list+`         │
└──────────┬───────────────────┘
           │
           ├─ For "eggs" (value 1)...
           │
           ▼
      ◆ logtest(score, 1)?
     ╱                    ╲
Yes │                      │ No
    ▼                      ▼
┌──────────────────┐     (continue)
│ Add "eggs" to    │
│ result_list      │
└──────────────────┘
    │
    ├─ For "peanuts" (value 2)...
    │
    ▼
 ◆ logtest(score, 2)?
╱                    ╲
... and so on ...
           │
           ▼
┌───────────────────┐
│ Return            │
│ result_list       │
└─────────┬─────────┘
          │
          ▼
         ● End

---

Where This Technique is Used in the Real World

Bitmasking isn't just for allergy tests. It's a fundamental pattern for any situation where you need to manage a fixed set of boolean flags efficiently. Its speed and low memory footprint make it invaluable in performance-critical domains.

• Operating Systems: The classic example is UNIX/Linux file permissions. The read (4), write (2), and execute (1) permissions for the owner, group, and others are stored using bitmasks. A file with `rwx` permissions for the owner (4+2+1=7) is a direct application of this concept.
• Databases: A single integer column can be used to store dozens of user preferences or settings, saving space and often allowing for faster queries using bitwise operators directly in SQL.
• Game Development & Graphics Programming: In engines like Unity or Unreal, and APIs like OpenGL or Vulkan, bitmasks are used everywhere. They control rendering states (e.g., enable depth testing, alpha blending, backface culling), physics collision layers, and input states. A single integer can represent which keys on a keyboard are currently pressed.
• Networking: Network protocols often use bitfields within packets to represent various flags and options in a compact form.
• Software Development: Feature flag systems can use bitmasks to represent which features are enabled for a particular user or environment, allowing for very fast checks in application code.

Mastering this concept from the Common Lisp learning path on kodikra.com provides you with a tool that transcends any single language and applies to the core of computer science.

---

Pros and Cons: When to Choose Bitmasking

Like any technique, bitmasking is a trade-off. It's incredibly powerful in the right context, but can be inappropriate in others. Understanding its strengths and weaknesses is key to being an effective developer.

Pros (Advantages)	Cons (Disadvantages)
Extreme Performance: Bitwise operations are single CPU instructions, making them one of the fastest ways to check and set flags.	Poor Readability: Code like if (flags & 0x10) is less intuitive for new developers than if (user.can_edit_posts). Good naming and constants are essential.
Memory Efficiency: A single 64-bit integer can store 64 distinct boolean flags, whereas an array of 64 booleans would take significantly more memory.	Limited Number of Flags: You are limited by the size of your integer (typically 32 or 64 flags). If you need hundreds of flags, this approach is not suitable.
Atomic Operations: On many architectures, updating a single integer is an atomic operation, which can simplify concurrent programming by avoiding the need for locks to update multiple flags.	Inflexibility: Adding a new flag can be difficult. If you run out of bits, you need to add a second integer, which complicates the logic. All flags must be known in advance.
Easy to Store/Transmit: A single number is trivial to serialize, store in a database, or send over a network compared to a more complex data structure.	Error-Prone: It's easy to make mistakes, such as using a flag value that is not a power of two, which would cause collisions with other flags.

Future-Proofing Your Approach: While bitmasking is timeless, modern systems often prioritize readability. For many web applications, a more descriptive approach like a set of keywords or a JSON object might be better. However, for performance-critical loops, embedded systems, or low-level library code, bitmasking remains the superior choice and is unlikely to be replaced. As of 2024 and beyond, its role in systems programming is secure.

---

Frequently Asked Questions (FAQ)

What exactly is bitmasking?

Bitmasking is the act of using an integer value, known as a "mask," to manipulate specific bits of another integer. By applying bitwise operations (like AND, OR, XOR, NOT) with a carefully crafted mask, you can set, clear, toggle, or query individual bits, effectively treating the integer as an array of booleans.

Why must the allergy values be powers of two?

Assigning values that are powers of two (1, 2, 4, 8, ...) ensures that each value corresponds to a single, unique bit in its binary representation. This prevents overlap. If peanuts were 2 and shellfish were 3 (binary 11), a score of 3 could mean "shellfish" or "peanuts and eggs," making the data impossible to decode reliably.

What does the logtest function do in Common Lisp?

logtest is a boolean function that checks if the bitwise AND of its two integer arguments is non-zero. It's a predicate specifically for this purpose. (logtest score mask) is equivalent to (not (zerop (logand score mask))), but is more direct and expressive for checking if any flags in the mask are set in the score.

How would I add a new allergy, like "tree-nuts," to this system?

To add a new allergy, you would pick the next available power of two (in our case, 256, since 128 is the last used value) and add a new entry to the +allergen-list+ constant: ("tree-nuts" . 256). The existing functions would work immediately with no other changes required, demonstrating the extensibility of the design.

Is bitmasking significantly faster than using a list of strings?

Yes, dramatically so. A bitwise AND is a single machine instruction that completes in a nanosecond or less. Checking for an element in a list of strings requires iterating through the list and performing string comparisons, which involves multiple memory lookups and character-by-character checks. For performance-critical code, the difference can be several orders of magnitude.

How should I handle scores that include unknown allergens?

Our current list-allergies implementation gracefully ignores them. A score of 257 would be 256 + 1. Our function would see the bit for 1 ("eggs") and the bit for 256. Since 256 is not in our +allergen-list+, it is simply skipped, and the function would correctly return a list containing only "eggs". This is a robust way to handle forward compatibility.

What are some alternatives to bitmasking in Common Lisp?

For situations where readability is more important than raw performance, you could use:

• A list of keywords: '(:peanuts :strawberries). Checking for an allergy would use (member :peanuts allergy-list).
• A hash table: With allergen names as keys and T as the value. This provides fast lookups, but with more memory overhead.
• A bit vector: Common Lisp's (make-array n :element-type 'bit) provides a true array of bits, which can be more intuitive if you need a very large number of flags.

---

Conclusion

The "Allergies" problem, sourced from the kodikra.com learning module, is a brilliant introduction to the world of bit-level data manipulation. By representing a collection of allergies as bits within a single integer, we unlocked a solution in Common Lisp that is not only correct but also exceptionally efficient. Using idiomatic tools like defconstant, logtest, and the loop macro, we built a system that is robust, readable, and performant.

More importantly, you've now mastered a technique that is fundamental to computer science. The next time you encounter a problem that requires managing a set of states, you'll recognize the opportunity to use bitmasking, saving memory and gaining speed. This is the kind of deep, foundational knowledge that separates a good programmer from a great one.

Disclaimer: The code in this article is written for modern Common Lisp implementations and has been validated against recent versions like SBCL 2.4.x. The core bitwise functions are part of the ANSI standard and are highly portable.

Ready to tackle the next challenge? Continue your journey on the Common Lisp learning path and discover more powerful programming paradigms. Or, if you want a broader view of the language, explore our complete guide to Common Lisp.

---

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