The basic idea of bitslicing, or SIMD within a register, involves two parts:
expressing the cipher in terms of single-bit logical operations (AND, OR, XOR, NOT, etc.), as if you were implementing it in hardware, and
carrying out those operations for multiple instances of the cipher in parallel, using bitwise operations on a CPU.
That is, in a bitsliced implementation, instead of having a single variable storing, say, a 32-bit number, you have one variable storing the lowest bit of the number (or, rather, of $n$ numbers, where $n$ is the number of bits your CPU can store in a register), another variable storing the second lowest bit(s) of the number(s), and so on.
Obviously, calculating everything bit-by-bit is (usually) a lot slower than just calculating things the ordinary way. But with an $n$-bit processor, a bitsliced implementation can run up to $n$ instances of the cipher (e.g. to encrypt up to $n$ blocks of data) in parallel. Thus, as long as the bitsliced implementation is no more than $n$ times slower to run a single instance of the cipher, you end up with a net gain in throughput.
So which kinds of operations work well with bitslicing, and which operations don't?
Bit shifts, rotations and other bit permutations become trivial in a bitsliced implementation, since they just correspond to relabeling variables. Thus, such operations effectively take no time at all in a bitsliced implementation. Since crypto code tends to use such operations a lot, this alone can be a huge win for bitslicing.
(However, this is only true for constant bit shifts. If the shift amount depends on the data being processed, bitslicing it becomes much harder.)
Bitwise logical operations like XOR tend to be near the break-even point. If you have two sets of 32 numbers, each of them with 32 bits, and you want to XOR them with each other, it doesn't really matter if you do it number by number or bit by bit — you'll need to do 32 XORs either way.
Of course, if your CPU has, say, 64-bit or 128-bit registers (like, say, any modern x86 CPU with SSE does), then you can carry out 64 or 128 bitsliced 32-bit XORs, still using only 32 XOR instructions. Thus, bitslicing may still win out for XOR, just because of the extra parallelism.
Addition and subtraction can also be implemented using bitwise logical operations, essentially by implementing an adder circuit. This requires up to five instructions per bit (two XORs, two ANDs and one OR/XOR) to implement a full adder, although this can sometimes be reduced depending on what instructions are available (e.g. something like three-input XOR and majority instruction could allow implementing a full adder in two instruction per bit) and what the result will be used for (e.g. if carry-save addition can be used). Thus, addition and subtraction tend to be somewhat less efficient in a bitsliced implementation, although the increased parallelism mentioned above may still compensate for this.
More complex arithmetic, like multiplication and division, can also in principle be implemented using bitslicing, but the resulting code may be very slow and complicated. Fortunately, these operations are rarely used in ciphers (although public-key crypto sometimes requires them).
Notably, though, (binary) Galois field multiplication is a lot easier to bitslice than ordinary multiplication, due to the absence of carries. Also, multiplication (whether ordinary or in a Galois field) by a constant can be decomposed into a combination of shifts (free!) and additions (or XORs), making it fairly easy to bitslice.
Table lookups are generally very hard to bitslice, for obvious reasons. However, if the look-up table is small and fixed, like the S-boxes in many ciphers, then it may be possible to replace it with a logical circuit that computes the same result, and bitslice that. This is how Eli Biham handled the S-boxes in their original 1997 bitsliced DES implementation, for example. Conveniently, optimized hardware S-box implementations can often be directly translated into bitsliced software implementation. Thus, any ciphers that can be efficiently implemented in hardware (which tends to be a common design criterion) can usually also be bitsliced well.
Conditional code (like
if statements) is also rather difficult to bitslice, although there are ways to emulate it with masking. For example, a conditional expression like
x = (condition ? a : b) may be rewritten as
x = (a & mask) | (b & ~mask), where
mask is set to all ones if
condition is true, and to all zeros otherwise, and then bitsliced.
A general advantage of bitslicing is that bitsliced code tends to run well on heavily pipelined modern CPU, since it tends to have a low risk of pipeline stalls and plenty of opportunities for optimal instruction reordering. Basically, in normal crypto code, if you calculate something like:
w = x + (y XOR z)
then the XOR calculation must finish before the addition can start, preventing the operations from executing in parallel. In a bitsliced implementation, however, we can e.g. calculate the low-order bits of the XOR first, and then move on to the high-order ones, so that when we start doing the addition, the low-order bits that we need first will have had plenty of time to get ready.
If we want, we can also e.g. interleave the XOR and addition calculations together (or just let the compiler do that for us), only calculating the XOR bits just in time to be ready when we need them for the addition. This can reduce the potential for stalls within the addition code, by letting the processor calculate the XORs while it's waiting for the carry bits to be ready, and may also improve register and/or cache locality.
Also, thanks to the elimination of conditionals, as described above, bitsliced code tends not to suffer from branch misprediction. Conveniently, this also tends to make it resistant to timing attacks, and thus more secure.
All that said, bitslicing also has its downsides. One is that, when processing $n$ instances of the cipher in parallel, you need to store $n$ copies of the cipher state. Thus, whereas in a conventional implementation you might be able to fit the full state in CPU registers, or at least in L1 cache, a bitsliced implementation will use a lot more space, and thus may end up pushing some data out to slower caches, or even to uncached RAM.
This issue can sometimes be partially alleviated by sharing data between cipher instances, e.g. when encrypting multiple data blocks with the same key. Also, clever instruction reordering (by the programmer or by the compiler) may improve cache locality, e.g. by computing multiple operations on, say, the low-order bits of the data (and so keeping the variables storing those bits in registers or in fast cache) before performing the same operations on other bits. Still, in general, a bitsliced cipher implementation is likely to have somewhat poorer cache locality than a non-bitsliced one.
Also, some algorithms just don't bitslice well. A notable example is the RC4 stream cipher, which seems almost designed to frustrate any bitslicing efforts:
It has a large internal state (258 × 8 = 2064 bits per cipher instance), most of which cannot be shared between instances, making a bitsliced implementation require a lot of memory.
Most of that state consists of a constantly changing 8-bit lookup table. Because the lookup table isn't fixed, it cannot be replaced by a logical circuit like, say, the S-boxes in DES or AES can.
Only 4 bytes of the state change per iteration, but one of the bytes that does change is, in effect, pseudorandomly chosen. Running many instances of RC4 in parallel would mean that, on every iteration, many bits of the state would change in some instance (but rarely in more than one).
In fact, I've sometimes wondered if RC4, or some similar algorithm, might not be useful as a deliberately unparallelizable and hardware-unfriendly component in an scrypt-like construction.