Posts

Problem statement

This problem was asked by Cisco.

Given an unsigned 8-bit integer, swap its even and odd bits. The 1st and 2nd bit should be swapped, the 3rd and 4th bit should be swapped, and so on.

For example, 10101010 should be 01010101. 11100010 should be 11010001.

Bonus: Can you do this in one line?

I’ve been commuting somewhat less than 3 days a week, from Fort Collins to Denver and back. I’ve seen some mighty strange stuff.

I thought that since the purely recursive implementation of mergesort didn’t show weird, abrupt performance drops, traversing linked lists (no matter what order the nodes appeared in memory) also did not show abrupt performance drops, and that node size in memory caused different performance oddities, that the iterative implementation’s memory access patterns might be the cause.

When my kids were small, I would tell them about famous philosophical or mathematical paradoxes.

I checked the effect of list element size on my implementation of mergesort of a linked list.

A museum and exhibit you should visit

Denver Museum of Nature and Science currently has an absolutely fascinating, traveling exhibit about Orcas.

It occurred to me that benchmarking traversing very long linked lists end-to-end might provide some clues.

Hailstones from 2016-07-15T17:14:00, Baker neighborhood, Denver, Colorado.

Based on the effects of linked list re-use, I checked if using a linked list with in-memory-address-order made a difference.