4 ms·

Great page. A few years ago I saw it posted here on HN and bookmarked it, and would play around with a few of the (simpler) examples every now and then. Last y

Great page. A few years ago I saw it posted here on HN and bookmarked it, and would play around with a few of the (simpler) examples every now and then. Last year I was in an interview and something around writing a program to find out if an integer is a power of 2 came up. I remembered the example from the doc above and used that (you basically AND your integer with itself minus one, which makes sense because any power of 2 is going to be 1 followed by some zeroes...see below). I got the job! 10000 & 1111 ______ 1

tslater2006 4y ago
> 10000 > & 1111 > ______ > 1 Wouldn't this result in 0 and not 1?
- knome 4y ago
  Missing a 'not'. You would use `bool( nn and not (nn&(nn-1)) )` Let's try for 15 start 0b1111 sans1 0b1110 anded 0b1110 not 0b0000 Now 8 start 0b1000 sans1 0b0111 anded 0b0000 not 0b0001 It's basically a claim that, in binary, only powers of two won't have any overlapping bits between the initial number and that number minus one. Doesn't work for 0 so you have to special case it.
- sumnole 4y ago
  0 is correct. AND(bit1,bit2) returns 1 if and only if both input bits are 1. AND'ing each bit of the two numbers yields only 0 bits: 10000 &01111 ______ 00000
fernly 4y ago
Hah. Back in the stone ages, I posed this question in my column at Dr. Dobb's Journal and I have never forgotten the best reply. The above algorithm in Forth is DUP DUP NEG AND =
deleted 4y ago
[deleted]
Jach 4y ago
For a while I experimented with giving easy problems like that during 'phone' screens (usually over google meet, with a shared text editor link), and whatever their first answer was I always asked if they could think of another way to implement it. I liked the simple "is this odd/even?" question, and could prod for alternates by asking to use or not use a loop/modulus. My favorite alternate answer was someone doing the bit-and moral equivalent in base 10 by converting the number to a string and checking the last character. I felt like it gave good bang-for-buck with respect to https://sites.google.com/site/steveyegge2/five-essential-phone-screen-questions https://sites.google.com/site/steveyegge2/five-essential-pho... in that it takes hardly any time, it's probably about as good as fizzbuzz in catching out applicants who for whatever reason literally can't seem to program (only encountered two of those but that was only after someone else had screened them and passed them on), and it's an opportunity to show awareness of the 'bit nature' of these things (not very important to the work and lacking it isn't a sufficient reason to reject, but all else equal, I'd rather take someone with that awareness than someone without).

tslater2006 4y ago

> 10000 > & 1111 > ______ > 1 Wouldn't this result in 0 and not 1?

knome 4y ago
Missing a 'not'. You would use `bool( nn and not (nn&(nn-1)) )` Let's try for 15 start 0b1111 sans1 0b1110 anded 0b1110 not 0b0000 Now 8 start 0b1000 sans1 0b0111 anded 0b0000 not 0b0001 It's basically a claim that, in binary, only powers of two won't have any overlapping bits between the initial number and that number minus one. Doesn't work for 0 so you have to special case it.
sumnole 4y ago
0 is correct. AND(bit1,bit2) returns 1 if and only if both input bits are 1. AND'ing each bit of the two numbers yields only 0 bits: 10000 &01111 ______ 00000

fernly 4y ago

Hah. Back in the stone ages, I posed this question in my column at Dr. Dobb's Journal and I have never forgotten the best reply. The above algorithm in Forth is DUP DUP NEG AND =

deleted 4y ago

[deleted]

Jach 4y ago

For a while I experimented with giving easy problems like that during 'phone' screens (usually over google meet, with a shared text editor link), and whatever their first answer was I always asked if they could think of another way to implement it. I liked the simple "is this odd/even?" question, and could prod for alternates by asking to use or not use a loop/modulus. My favorite alternate answer was someone doing the bit-and moral equivalent in base 10 by converting the number to a string and checking the last character. I felt like it gave good bang-for-buck with respect to https://sites.google.com/site/steveyegge2/five-essential-phone-screen-questions https://sites.google.com/site/steveyegge2/five-essential-pho... in that it takes hardly any time, it's probably about as good as fizzbuzz in catching out applicants who for whatever reason literally can't seem to program (only encountered two of those but that was only after someone else had screened them and passed them on), and it's an opportunity to show awareness of the 'bit nature' of these things (not very important to the work and lacking it isn't a sufficient reason to reject, but all else equal, I'd rather take someone with that awareness than someone without).