Articles from 2009 - Exploring Binary

Powers Of Two In The Josephus Problem

By Rick Regan July 24th, 2009

Pradeep Mutalik of The New York Times recently blogged about a puzzle that is an instance of the Josephus Problem. The problem, restated simply, is this: there are n people standing in a circle, of which you are one. Someone outside the circle goes around clockwise and repeatedly eliminates every other person in the circle, until one person — the winner — remains. Where should you stand so you become the winner?

Here’s an example with 13 participants:

Alternating Elimination with 13 people, order of elimination shown in red (winner is person 11)

As Pradeep and his readers point out, there’s no need to work through the elimination process — a simple formula will give the answer. This formula, you won’t be surprised to hear, has connections to the powers of two and binary numbers. I will discuss my favorite solution, one based on the powers of two.

Continue reading “Powers Of Two In The Josephus Problem”

Google Image Matches the Imagery of Exploring Binary

By Rick Regan July 20th, 2009

The image on Google’s home page today, which commemorates the 40th anniversary of the moon landing, matches the imagery of this site:

Partial Screenshot of Google's Home Page, July 20, 2009

Continue reading “Google Image Matches the Imagery of Exploring Binary”

Visualizing Consecutive Binary Integers

By Rick Regan July 2nd, 2009

The following is a visual depiction of the binary integers 0 through 11111111:

A nice pattern, right? I generated it based on the image found on page 117 of Stephen Wolfram’s “A New Kind of Science”. I’ll discuss its structure in detail in this article.

Continue reading “Visualizing Consecutive Binary Integers”

Decimal/Binary Conversion Table

By Rick Regan June 30th, 2009

Here is a table you can use to convert small integers — integers between 0 and 255 — directly between decimal and binary (as an alternative to using a decimal/binary converter):

Continue reading “Decimal/Binary Conversion Table”

Nines in Binary

By Rick Regan June 10th, 2009

I discovered a cool property of positive integers of the form 10ⁿ-1, that is, integers made up of n digits of 9s: they have binary representations that have exactly n digits of trailing 1s. For example, 9,999,999 in decimal is 100110001001011001111111 in binary.

The property is interesting in and of itself, but what is more interesting is the process I went through to discover it. It’s a small-scale example of experimental mathematics: I observed something interesting, experimented to collect more data, developed a hypothesis, and constructed a proof.

Continue reading “Nines in Binary”

Doing Decimal/Binary Conversions with Wolfram Alpha

By Rick Regan May 29th, 2009

Wolfram Alpha can do many types of calculations, including conversions between numbers in different bases. I’ll demonstrate by showing examples of decimal to binary and binary to decimal conversion.

Continue reading “Doing Decimal/Binary Conversions with Wolfram Alpha”

How I Taught My Mother Binary Numbers

By Rick Regan May 26th, 2009

I introduced my mother to binary numbers a few weeks ago when I showed her my One Hundred Cheerios in Binary poster. It shows the decimal number 100 in binary — 1100100. She’s not an engineer but she’s good with numbers, so I knew she would get it — if only I could find the right way to explain it. Two days ago, I found the right way.

Continue reading “How I Taught My Mother Binary Numbers”

Displaying the Raw Fields of a Floating-Point Number

By Rick Regan May 20th, 2009

A double-precision floating-point number is represented internally as 64 bits, divided into three fields: a sign field, an exponent field, and a fraction field. You don’t need to know this to use floating-point numbers, but knowing it can help you understand them. This article shows you how to access those fields in C code, and how to print them — in binary or hex.

Continue reading “Displaying the Raw Fields of a Floating-Point Number”

Converting Floating-Point Numbers to Binary Strings in C

By Rick Regan May 6th, 2009

If you want to print a floating-point number in binary using C code, you can’t use printf() — it has no format specifier for it. That’s why I wrote a program to do it, a program I describe in this article.

(If you’re wondering why you’d want to print a floating-point number in binary, I’ll tell you that too.)

Continue reading “Converting Floating-Point Numbers to Binary Strings in C”

Base Conversion in PHP Using BCMath

By Rick Regan April 11th, 2009

PHP has a component called BCMath which does arbitrary-precision, decimal arithmetic. I used BCMath in my decimal/binary converter because:

Arbitrary-precision lets it operate on very large and very small numbers, numbers that can’t be represented in standard computer word sizes.
Decimal arithmetic lets it use the same algorithms I’d use to convert between decimal and binary by hand.

(If you’ve written a conversion routine in standard code, especially one to convert decimal fractions to binary, you’ll see the advantage of the second point.)

This article describes the implementation of my conversion routines with BCMath.

Continue reading “Base Conversion in PHP Using BCMath”

Base Conversion In PHP Using Built-In Functions

By Rick Regan April 7th, 2009

The PHP programming language has many built-in functions for converting numbers from one base to another. In fact, it has so many functions that it can be hard to know which to use. Some functions have similar capabilities, and some work with parameters of different types. We’ll sort through the differences in this article, and explain the proper context in which to use each function.

Continue reading “Base Conversion In PHP Using Built-In Functions”

Elements of Binary in the NCAA Basketball Tournament

By Rick Regan March 11th, 2009

If you’re a sports fan, you think of basketball when you see this:

Diagram of the NCAA Basketball Tournament — Basketball or Binary?

If you’re like me, you also think of powers of two, binary trees, logarithms, laws of exponents, geometric sequences, geometric series, and Bernoulli trials — in short, the elements of binary numbers, binary code, and binary logic.

I hope you’re thinking: “wow — all that math stuff I hated actually has a practical use!”

Continue reading “Elements of Binary in the NCAA Basketball Tournament”