reversing a long

This is the other question I was asked. The straightforward method: loop 64 times, shift out from right, shift in from left. This means 128 shift operations, and 64 ANDs, 64 ORs.

My brain, of course, wouldn't let go, so I came up with something much more elegant, somewhere, half asleep on the plane:

public static final long reverse(long l) {
l = (l>>32)|(l<<32);
l = ((l>>16)&0x0000ffff0000ffffl)|((l<<16)&0xffff0000ffff0000l);
l = ((l>>8)&0x00ff00ff00ff00ffl)|((l<<8)&0xff00ff00ff00ff00l);
l = ((l>>4)&0x0f0f0f0f0f0f0f0fl)|((l<<4)&0xf0f0f0f0f0f0f0f0l);
l = ((l>>2)&0x3333333333333333l)|((l<<2)&0xccccccccccccccccl);
l = ((l>>1)&0x5555555555555555l)|((l<<1)&0xaaaaaaaaaaaaaaaal);
return l;
}

This is 12 shifts, 10 ANDs, 6 ORs.

parity

I got the question, of how do you compute the parity of an int? My first reaction was that, well, you make a loop, 32 times, shift right, and do an xor on the least significant bit. I mean, man, that is an easy question, why do you even ask?

I'm ashamed to say, that I should have thought more carefully. I woke up in the middle of the night, 8 hours later, and had a relevation:


public static final int parity(int i) {
i = (i>>16)^i;
i = (i>>8)^i;
i = (i>>4)^i;
i = (i>>2)^i;
i = (i>>1)^i;
return i&1;
}


using NTFS for my external hard drive

I bought a 250GB external hard drive. Since sometimes I need to plug it into Windows PCs, I decided it is best to have it formatted as NTFS. I installed ntfs drivers (yum install ntfs-3g), and voilá, when I plugged it into the USB port, a nice folder appeared on my Gnome desktop, and everything was accessible.

Except for it is all read-only.

Damn. Now I need to figure out who is to blame: ntfs-3g, fuse, or gnome-mount.

Update, the fix is a one-liner:
gconftool-2 -s /schemas/system/storage/default_options/ntfs/mount_options -t string '[uid=]'

linux on my usb stick

Interesting excercise. The stick can hold 512MB, so my first thought (put the Ubuntu live CD onto the stick) failed.

So here's what I figured out:

• debootstrap is your friend. You partition, format, mount, debootstrap, and have a functional linux.
• oh. De only thing you don't have, is an actual linux kernel. So install it with apt-get
• both lilo and grub is complicated and big. Use extlinux to boot
• apt-get install xserver-xfree-drv-ati, and some fonts
  
• apt-get install gnome - this is 700MB! who would have thought. skip that
  
• I settled with apt-get install fvwm. Oh the old days
  
• apt-get install xdm - why does this also install cpp??
• and to get to the point: apt-get install firefox

Tadaam. Still got 100MB to spare, and can do all my stuff. I mean you can do everything with a browser, can't you :)

Dusting off C

Since I'm looking for a job, I started practicing C coding. So yesterday I've implemented:

• bubble sort in array
• quickshort in array
• heapshort in array
• search for optimal parenthesing of matrix multiplication
• radix short of a linked list
• binomial heap addition

Today, I'll have a look at Perl :)

Quiz

I just saw ad in the Budapest subway. It is looking for employees, Google-style.


I couldn't figure out the solution from the top of my head. What is the execution order of the "p2(c++), p1(c)" part? When will the variable c be incremented? What will be the calling order of the p1,p2 constructors? C++ is one magic language with lots of arbitrary rules.

But, of course, I typed it in and got the solution.