Binary Addition
(Published January 30th, 2012) This is the first of a four part series on binary arithmetic, which I’m writing as a supplement to my binary calculator. This article introduces binary arithmetic, and then discusses binary addition.
Example of Binary Addition
Articles in the ‘Binary numbers’ Category
Binary Numbers Haiku
I wrote these haiku about binary numbers:
Binary numbers,
they are just zeros and ones.
Switches — on and off!
they are just zeros and ones.
Switches — on and off!
How I Taught Third Graders Binary Numbers
Last week I introduced my son’s third grade class to binary numbers. I wanted to build on my prior visit, where I introduced them to the powers of two. By teaching them binary, I showed them that place value is not limited to base ten, and that there is a difference between numbers and numerals.
My presentation was based on base-ten-block-like imagery, since I knew the students were comfortable expressing numbers with base ten blocks. I thought extending the block model to other bases would work well. I think it did.
The Number Twenty-Seven in Tape Flags, Broken Into Powers of Two
In Search of Decimal/Binary/Hexadecimal Palindromes
Are there any multiple digit hexadecimal number palindromes that are also palindromic in binary and decimal? I have been searching but have not found any.
I started my search with my program that finds multiple-base palindromes. I generated palindromes in binary, and then checked them to see if they were also palindromes in hexadecimal and decimal. I looked for decimal/binary/hexadecimal palindromes up to 16 hex digits long, but did not find any.
To continue my search into bigger numbers, I wrote a program that uses arbitrary-precision integer arithmetic and a more efficient algorithm. Despite being able to search much further, I still have not found any.
In this article, I’ll analyze the size of the palindrome “search space”, explain my improved algorithm, and discuss the state of my search.
Counting Binary/Hexadecimal Palindromes
In my article “Counting Binary and Hexadecimal Palindromes” I derived formulas for counting binary palindromes and hexadecimal palindromes. For each type of palindrome, I derived two pairs of formulas: one pair to count n-digit palindromes, and one pair to count palindromes of n digits or less.
In this article, I will derive similar formulas to count binary/hexadecimal palindromes — multi-base palindromes I’ve shown to have an algorithmically defined structure.
The Structure of Binary/Hexadecimal Palindromes
Binary/hexadecimal palindromes are integers that are palindromic in both binary and hexadecimal. Unlike binary/decimal palindromes, for example, they have a predictable structure. This means they can be generated directly, rather than searched for. So what is their structure?
Certainly they’re made up of the hexadecimal digits that are themselves palindromic in binary: 0, 6, 9, F; for example, F060F16 = 111100000110000011112 and 9F916 = 1001111110012. Each of these four hexadecimal digits maps neatly to a 4-digit binary palindrome, so any hexadecimal palindrome made from them is automatically palindromic in binary.
But there are other binary/hexadecimal palindromes, like 52516 = 101001001012 and 7020716 = 11100000010000001112, that contain hexadecimal digits that are not palindromic in binary. In this case, binary palindromes are produced with combinations of hexadecimal digits. It turns out there are a limited number of valid combinations, and that they’re localized — they span only two hexadecimal digits.
In this article, I’ll analyze binary/hexadecimal palindromes and describe their structure — a structure due to the relationship of the two bases, binary and hexadecimal.
Example Binary/Hexadecimal Palindromes
Counting Binary and Hexadecimal Palindromes
How many nonzero, n-digit, decimal number palindromes are there? These two formulas give the answer:
- When n is even: 9·10n/2-1
- When n is odd: 9·10(n+1)/2-1
How many nonzero, decimal number palindromes are there, consisting of n-digits or less? These two formulas give the answer:
- When n is even: 2(10n/2 – 1)
- When n is odd: 11·10(n-1)/2 – 2
So for example, there are 900 5-digit decimal palindromes, 9,000 8-digit decimal palindromes, 1,098 decimal palindromes of 5 digits or less, and 19,998 decimal palindromes of 8 digits or less.
In this article, I will derive similar formulas to count binary and hexadecimal number palindromes.
Binary Dates in 2010 and 2011
People have been tweeting about the upcoming dates that look like binary numbers. 10/10/10 seems to be a favorite, both because of its symmetry and because 101010 = 42 in decimal (you know, the answer to the ultimate question of life, the universe, and everything). Here are the nine dates in 2010, interpreted as binary numbers, and with their decimal equivalents:
Nines in Quinary
In my article “Nines in Binary”, I proved the following: positive integers of the form 10n-1, that is, integers made up of n digits of 9s, have binary representations with exactly n digits of trailing 1s. Pat Ballew made a clever observation, adapting my result to prove an equivalent statement for base 5 (quinary): positive integers of the form 10n-1 have quinary representations that have exactly n digits of trailing 4s. For example, 9999 in decimal is 304444 in quinary.
In “Nines in Binary”, I derived an expression for 10n – 1 that shows its structure as a binary number:
10n – 1 = (5n – 1) 2n + (2n – 1)
Pat derived a similar expression for 10n – 1 that shows its structure as a quinary number:
10n – 1 = (2n – 1) 5n + (5n – 1)
In essence, he swapped the 2s and 5s, making it the “dual” of my formula, if you will.
I’ll show the details of the derivation and prove why the formula works.
Finding Numbers That Are Palindromic In Multiple Bases
A palindromic number, or number palindrome, is a number like 74347, which is the same written forward and backward.
A number can be palindromic in any base, not just decimal. For example, 101101 is a palindrome in binary. A number can also be palindromic in more than one base, like decimal 719848917, which is 101010111010000000010111010101 in binary and 5272002725 in octal.
An efficient way to find palindromes in a single base is to generate them, iterating through each integer and constructing palindromes from them. An efficient way to find numbers that are palindromic in multiple bases is to take a palindrome in one base and test if it’s a palindrome in one or more additional bases.
In this article, I’ll show you C code I wrote that finds multi-base numeric palindromes. I used this code to generate tables of numbers that are palindromic in decimal and binary, decimal and hexadecimal, and decimal and octal. I also used this code to solve Euler problem 36, which asks for the sum of all numbers, less than one million, that are palindromic in decimal and binary.
Visualizing Consecutive Binary Integers
The following is a visual depiction of the binary integers 0 through 11111111:
Binary Integers 0-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.
Decimal/Binary Conversion Table
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):
