Fog Creek Software
Discussion Board




Fun with bits

A few new challenges on bit shifting and twists on existing ones:

http://beust.com/weblog

Cedric
Monday, July 26, 2004

Hey, that was my homework last week in Ray Mitchell's Advanced C/C++ class at UCSD!

http://www.meanoldteacher.com/Cpp2/Cpp2Programming.htm

Sassy
Monday, July 26, 2004

My feeling about these little bit-twiddling questions on interviews are very mixed.

On the one hand, I am really good at answering them, so that's cool for me.

On the other hand, I can't remember the last time I did anything even remotely similar to this sort of thing in real world code (uh, clear the right-most bit... yeah that one comes up all the damn time! uh.. wait, no it doesn't), which makes me think these questions are becoming ever more increasingly obsolete for the vast majority of programmers.

Mr.Fancypants
Monday, July 26, 2004

"I know these tricks, and if you know these tricks too, then you must be as smart as me, which is very smart indeed!"

That's all that means in an interview. Mine is "how can you tell if two date ranges overlap without looping?" Joel's is "reverse a string in place" Yes, the interviewee can figure them out on their own, and it's more likely the smarter they are/more experiece they have, but it's when the supplicant, er, applicant can jot the answer down directly that we are most pleased with them and give them a treat.

[shrug] Learn a trick and show it off on command - are we hiring show dogs?

Philo

Philo
Monday, July 26, 2004

And if you liked those:

http://aggregate.org/MAGIC/

Tom
Monday, July 26, 2004

I'm an ASIC developer. Actually we do these kinds of operations in C++ a lot!

Mtl_Dev
Monday, July 26, 2004

Clear the rightmost bit - surely it's missing the obvious

x = x & ~1;

option. (or x & -2 even).

These things are useful if you do any assembly code or low-level stuff with hardware...

Matt
Monday, July 26, 2004

ASIC, Assembly, silicon - I'm not going to argue the essential necessity of understanding The Boolean Way.

However, the title of the guy's blog is
"Thoughts on J2EE, Java, AOP and software development in general"

I'll venture in 4GL land, it isn't really that critical. I could be wrong. :-)

Philo

Philo
Monday, July 26, 2004

One of my favourite interview questions is how do you eliminate duplicate rows from a table, in SQL Server (for example).

There are lots of possible correct answers, but many candidates seem to opt for one of the incorrect answers instead, or just give up without trying.

One guy, who was interviewing for a data migration/cleansing job said he would open the table in Access and identify the duplicates visually. Fine I said, good answer if we have ten rows, how about ten million ? He couldn't come up with a better solution than just looking at them and removing the duplicates manually in Access.

I know that these are all "trick questions", but I still reckon someone interviewing for that role should know at least one feasible solution.

Nemesis
Monday, July 26, 2004

I think he wanted to clear the rightmost set bit. So x&~1 will only work for odd numbers. And for odd numbers, x&~1 is x-1, hence x-(x&1).

Tom
Monday, July 26, 2004

I agree about the trickness. These are tricksy, but it should be possible, perhaps with the right prodding, to draw the solution out of an interviewee who doesn't know the answer already. At the very least, they should immediately start trying various bitwise things rather than floundering randomly.

But I think this kind of thing is mainly appropriate for interveiwing junior people with little or no experience? Past a certain level you're surely more concerned with things other than whether they can do some &|~^ madness, and it would for sure be a better use of their time (and their employer's money) to look it up in a book.

Mind you, I've (thankfully) never had to do any interviewing. (my worry is mainly that i don't have enough bastard hard questions :)

Tom
Monday, July 26, 2004

The funny thing about these questions is that I think all my answers would be "I'd build a 256-byte lookup table, set up like <insert correct set for this problem>, and look up the results in a constant number of instructions."

Chris Tavares
Monday, July 26, 2004

I must be programming different applications from you guys. Bit twiddling comes up all the time in my stuff,

e.g. From many

Compression
Imaging
The ListView SetItemState etc WinAPI calls

The 256 look up table (and lookups for math results in general) are a surprisingly under-used technique. I probably wouldn't use them for the super simple bit ops though, unless the profiler guided me to that section.

S. Tanna
Monday, July 26, 2004

Show Dogs don't do tricks.

Clutch Cargo
Tuesday, July 27, 2004

Nemesis : I think that question is ok only if you give them some example data and explain the context. This is a problem that I have often had to deal with and it allways varies depending on the context.

Gary van der Merwe
Tuesday, July 27, 2004

nemesis: if the table has a primary key, then there will not be duplicate rows.
if the table does not have a primary key, i would create a table  with the same structure but with a primary key (i select one or more of the existing fields as primary key) , then i would move rows one by one ( with the aid of a program of course), all not repeated rows will go to new table, all rejected rows will go to a report.

PK
Tuesday, July 27, 2004

nemesis:

at last a usage of 'having' eh?

i like i
Tuesday, July 27, 2004

i like i, one of the few uses, I would say.

Nemesis
Tuesday, July 27, 2004

When pressed for extra information, which is a good sign, I explain like this:

Consider a table ("Customers") with just a single column ("ID" int not null). There are, say 10,000,000 rows, and you cannot apply a primary key, so at least one duplicated row exists. How do you identify and remove the duplicates ?

As mentioned above, there are many solutions and I am more interested in thought process than anyone claiming to have the "best" solution (there still isn't enough information to know what the "best" solution would be).

Nemesis
Tuesday, July 27, 2004

I use bit operations to set and read flag bits.

Tom:
You said he wants to clear the right-most set bit, but one of his examples was a shift right, shift left, which is only the right bit.

Steamrolla
Tuesday, July 27, 2004

Gods, you're right. I looked again. That's me being scared out of thinking about it properly after seeing those complicated-looking expressions. But today it is all very clear.

Sorry about that.

(x&~1 it is then. It never occurred to me it could get so complicated.)

Tom
Tuesday, July 27, 2004

Yeah, x & ~1 is just anding it with

1111111111..111110

which is clearly going to do the job, for clearing the LSB.

For clearing the rightmost /set/ bit, I think

x & (x-1)

will do the trick.

Matt
Wednesday, July 28, 2004

*  Recent Topics

*  Fog Creek Home