Hacker's Delight

Henry S. Warren

Mentioned 6

Compiles programming hacks intended to help computer programmers build more efficient software, in an updated edition that covers cyclic redundancy checking and new algorithms and that includes exercises with answers.

More on Amazon.com

Mentioned in questions and answers.

I've got a perfect binary tree that's enumerated the post-order way. An example of such tree would be

                         15
                 7               14
             3       6       10      13
           1   2   4   5    8  9   11  12

The size of the tree is known to me. I'm looking for a formula or a simple algorithm that would take a single number as an input (the ID of the vertex I'm interested in) and return also a single number - the ID of the parent. It's quite easy to traverse the tree from the top and get the result in O(log n). Is there a faster solution? I'm mostly interested in the leaves, so if there's a solution for the special case, bring it on too.

Sorry for the non-answer answer, but I don't think it's possible to do it in less than O(log n), even allowing for constant-time arithmetic and bitwise logical ops.

Each bit in the node's index potentially has an effect on nearly every left/right/stop decision in the traversal from the node to the root, including the first one. Moreover, examining the indices of the nodes at each level of the tree, they are aperiodic (and not only in powers of 2). This means (I think) that a constant number of arithmetic ops is not sufficient to identify the level, or whether the node is a left or right child.

It's a fascinating problem, though, and I'd love to be proven wrong. I just scoured my copy of Hacker's Delight -- I had high hopes for some of the exotic number bases they play with, but nothing quite fit.

I want to make plots like these from Hacker's Delight:

enter image description here

What ways are there to accomplish this in Python? A solution that makes it easy to interactively adjust the graph (changing the slice of X/Y currently being observed) would be ideal.

Neither matplotlib nor the mplot3d module have this functionality AFAICT. I found mayavi2 but it's extremely clunky (I can't even find the option for adjusting the sizes) and only seems to work correctly when run from ipython.

Alternatively gnuplot could work, but I'd hate to have to learn another language syntax just for this.

Since the example pointed out by TJD seemed "impenetrable" here is a modified version with a few comments that might help clarify things:

#! /usr/bin/env python
from mpl_toolkits.mplot3d import Axes3D
import matplotlib.pyplot as plt
import numpy as np
#
# Assuming you have "2D" dataset like the following that you need
# to plot.
#
data_2d = [ [1, 2, 3, 4, 5, 6, 7, 8, 9, 10],
            [6, 7, 8, 9, 10, 11, 12, 13, 14, 15],
            [11, 12, 13, 14, 15, 16, 17, 18 , 19, 20],
            [16, 17, 18, 19, 20, 21, 22, 23, 24, 25],
            [21, 22, 23, 24, 25, 26, 27, 28, 29, 30] ]
#
# Convert it into an numpy array.
#
data_array = np.array(data_2d)
#
# Create a figure for plotting the data as a 3D histogram.
#
fig = plt.figure()
ax = fig.add_subplot(111, projection='3d')
#
# Create an X-Y mesh of the same dimension as the 2D data. You can
# think of this as the floor of the plot.
#
x_data, y_data = np.meshgrid( np.arange(data_array.shape[1]),
                              np.arange(data_array.shape[0]) )
#
# Flatten out the arrays so that they may be passed to "ax.bar3d".
# Basically, ax.bar3d expects three one-dimensional arrays:
# x_data, y_data, z_data. The following call boils down to picking
# one entry from each array and plotting a bar to from
# (x_data[i], y_data[i], 0) to (x_data[i], y_data[i], z_data[i]).
#
x_data = x_data.flatten()
y_data = y_data.flatten()
z_data = data_array.flatten()
ax.bar3d( x_data,
          y_data,
          np.zeros(len(z_data)),
          1, 1, z_data )
#
# Finally, display the plot.
#
plt.show()

I need to find the largest power of 2 less than the given number.
And I stuck and can't find any solution.

Code:

public class MathPow
{
   public int largestPowerOf2 (int n)
   {
        int res = 2;        
        while (res < n) {
                res =(int)Math.pow(res, 2);
        }

        return res;
   }
}

This doesn't work correctly.

Testing output:

Arguments Actual Expected
-------------------------
9         16     8       
100       256    64      
1000      65536  512     
64        256    32      

How to solve this issue?

Integer.highestOneBit(n-1);

For n <= 1 the question doesn't really make sense. What to do in that range is left to the interested reader.

The's a good collection of bit twiddling algorithms in Hacker's Delight.

I'm familiar with C/C++ and assembly x86/x64 language, but now I need to study graphic optimizations (SSE/SSE2 and asm optimizations in general), what resources/books/links may I use to learn these topics? I've been searching across the web without much luck

Marco,

Three point response below :

  1. If you want to learn a set of quick tricks, there are books available under general titles of algorithmic puzzles. The following two I have used and provide excellent challenge set to hone your skills. Book1 is a collection of some very interesting tricks. I also enjoyed this Book2.

Prof Agner's posts I think are the last word on the subject and they are a must read.

  1. If you are seeking specifics of how to optimize, or use the 64 bit instruction set - my experience has been is to keep the Intel Manual Vol 2 handy. You may raise a specific question in this forum and get some excellent solutions. If you are seeking to start at a little more basic level, there is an excellent set of youtube tutorials by WhatsACreel - the coverage and explanations are superb. He takes you to AVX/AVX2 set over 60 odd sessions starting from basics.

  2. I am not a professional programmer - I am a businesses management professional, but write 64 bit assembly language codes for academic institutions/folks whose PhD's are stuck or suffering/some such people in this ilk/ in my spare time. I think x64 is extremely powerful, beautifully compact, and does what no language can try and do. So, if anyone is trying to discourage you from writing in x64, citing complexity, or whatever else, please show them a disassembly of code generated by any compiler of their own choice :-) (should scare them enough) or, just gently ignore them.

All the best,

Basicly I just need to know the position of the highest 1 bit inside of an int or unsigned int. Like:

00001111=4;
00011111=5;
11111111=8;

Because I am sure that any number I will get will have consecutive 1 bits. 0...0000011...1 There will be no ..00010011... or something. So method can find the highest 1 or just count 1s. No matter.

This is the best I managed to do:

Uint32 number;
int shift=16; int segment=8;
while (segment) 
{
if (number>>shift!=0) shift+=segment; 
else shift-=segment;
segment>>1; // /2
}

Others have given a variety of answers, but it's probably worth mentioning that there is an entire book full of these kinds of things — Hacker's Delight by Henry S. Warren Jr., ISBN 978-0-201-91465-8, which also has a web page.

It's also worth highlighting the fact that some microprocessors have special support for some of these kinds of things. Lasse Reinhold's answer, above, makes use of that fact, but doesn't call the reader's attention to it. Generally speaking, except for very simple cases (like bit rotate instructions), compilers can't optimise “bit twiddling” algorithms to a single machine instruction, so if you know you’re on a machine that has e.g. a bit-scan-forward or population count instruction or similar, and you're in a position to use it (via either compiler intrinsics or asm statements), you might want to do so.

Finally, since the question started by saying that the number was known to be of the form 0...000111...1, I'll add another option, based on computing (in parallel) the sums of the groups of bits:

uint32_t count_set_bits(uint32_t x) {
  x = ((x >> 1) & 0x55555555) + (x & 0x55555555);
  x = ((x >> 2) & 0x33333333) + (x & 0x33333333);
  x = ((x >> 4) & 0x0f0f0f0f) + (x & 0x0f0f0f0f);
  x = ((x >> 8) + x) & 0x00ff00ff);
  return (x >> 16) + x) & 0x0000ffff;
}

I know and understand the result.
For example 7 (decimal) = 00000111 (binary)
and 7 >> 2 = 00000001 (binary)
00000001 (binary) is same as 7 / 4 = 1
So 7 >> 2 = 7 / 4

But I'd like to know how this logic is created.
Can anyone elaborate on this logic ?
(Maybe it's just popped up in a genius head ?)

And is there any other similar logics like this ?

It didn't "pop-up" in a genius' head. Right shifting binary numbers would divide a number by 2 and left shifting the numbers would multiply it by 2. This is because 10 is 2 in binary. Multiplying a number by 10(be it binary or decimal or hexadecimal) appends a 0 to the number(which is effectively left shifting). Similarly, dividing by 10(or 2) removes a binary digit from the number(effectively right shifting). This is how the logic really works.

There are plenty of such bit-twiddlery(a word I invented a minute ago) in computer world.

http://graphics.stanford.edu/~seander/bithacks.html Here is for the starters.

This is my favorite book: http://www.amazon.com/Hackers-Delight-Edition-Henry-Warren/dp/0321842685/ref=dp_ob_image_bk on bit-twiddlery.