### Nomenclature, and data structures

First, I should correct my terminology. All computers are binary these days; Setun was a one-shot, and the days of BCD-based computers are long gone.

This is the case of

Of course, n-digit binary numbers map exactly to the elements of the power set of a set of n elements, so we can represent our generated combinations (

Maybe we can use a trick: consider a number

(The Haskell bitwise "and" and "or" are a little funky-looking.)

Well, if

So, you can write an

and then peel the bits off one at a time. To do that, we shouldn't just give back the LSB, because we're generating the next value in the sequence while we're at it, so

and we can pull them off until we end up with zero...

This is the case of

**noTwos**, and we've already dealt with the one case where a 3 can appear, so all the digits are either zero or one. So there's an obvious correspondence between these decimal palindromes and binary palindromes, pairing palindromes whose printable representations in their respective bases are equal.Of course, n-digit binary numbers map exactly to the elements of the power set of a set of n elements, so we can represent our generated combinations (

*vide*the function**choices**) as binary numbers. This is pretty tempting as an alternative to a**[Int]**, but I don't want to iterate over all those bits to see which are set. After all, if we're just doing half of the palindrome, and we know the most significant digit has to be 1, that leaves at most three bits on.Maybe we can use a trick: consider a number

**n**of a type in the**Bits**class. What can we say about**n .&. (n - 1)**?

Well, if

**n == 0**, the result is zero; otherwise, n has some bits set, and one of them is the least-significant bit.**n - 1**will have a zero in that position, and the more significant bits will be unchanged. The "and" gets rid of the trailing ones in case the least significant bit of**n**isn't in the ones position.So, you can write an

**lsb**function:**import Data.Bits**

lsb :: (Bits a) => a -> a

lsb n = n `xor` (n .&. (n - 1))lsb :: (Bits a) => a -> a

lsb n = n `xor` (n .&. (n - 1))

and then peel the bits off one at a time. To do that, we shouldn't just give back the LSB, because we're generating the next value in the sequence while we're at it, so

**bitStrip :: (Bits a) => a -> (a, a)**

**bitStrip n = (lsb, leftovers)****where leftovers = n .&. (n - 1)****lsb = n `xor` leftovers**and we can pull them off until we end up with zero...

**but**we still have to map over to base 10; that**lsb**is 2^i for some i. I'm not sure whether the LSB trick will help any.
## Comments