1
$\begingroup$

I'm looking for introductory resources--web pages, book chapters, articles--that introduce the C language with an immediate focus on bit-twiddling functions (e.g. bitwise XOR, AND, shifts), and of course branching and looping, but with very little discussion of large scale program structure (e.g. header files), pointers, or complex data structures. Alternatively, a general, non-C intro to low-level manipulation of bit sequences would be useful. The idea is to introduce someone to the logic of algorithms that manipulate bit strings, without them having to learn to program. I may end up writing something like this myself, but I thought a better version might already exist. Any suggestions would be welcome.

(If this question is inappropriate for scicomp.SE, feel free to say so, and I'm sure downvotes or close votes will let me know. I'll delete the post in that case. I don't think there's another SE site that would be appropriate--I've looked--but that's not your problem. :-)

Why:

I'm a philosopher of science working on a project that uses ideas from the literature on pseudorandom number generating algorithms to argue for certain conclusions in philosophy of science. Sometimes these algorithms are presented mathematically, or by other methods that can be understood by non-coders. However, articles on PRNGs often present algorithms using C or C-inspired pseudocode (example: Mersenne Twister paper). The subset of C that's used in this sort of code is usually very limited; in my experience, it often makes no significant use of pointers or structs or some other things that an introduction to C is likely to want students to learn early on.

I would like to be able to send other philosophers of science and scientists who are comfortable with formal logic and math to an introductory resource on C with bit-twiddling functions. These would be people who are comfortable with formal representations but are not coders, and probably don't know much about how numbers are represented and processed in hardware. However, you don't have to become a programmer to understand a description of a PRNG algorithm as a representation in a quirky formal logical language--i.e. a subset of C--for manipulation of sequences of bits, i.e. Booleans. I think there are ideas from the PRNG literature that will be of interest to some philosophers of science and scientists who are not coders, and I want to help them over the hump of thinking that they can't read algorithms in C without learning to program.

$\endgroup$
1
$\begingroup$

Bit-twiddling is sometimes used as part of the numerical algorithms that are apropos for this site (e.g., hardware implementations of the Fast Fourier Transform, simulation of quantum computers, etc.).

Some resources that come to mind:

  1. D. E. Knuth, The art of computer programming. Vol. 4A. Combinatorial algorithms.

  2. H. Warren, Hacker's delight.

  3. https://web.archive.org/web/20191008012414/http://home.pipeline.com/~hbaker1/hakmem/hakmem.html

$\endgroup$
1
  • 1
    $\begingroup$ I should have thought to look at Knuth. I'm only familiar with volume 2, or rather chapter 3. $\endgroup$
    – Mars
    Feb 25 at 8:04

Not the answer you're looking for? Browse other questions tagged or ask your own question.