Archives, eh
-
# la résolution des problèmes de l'escalier
I was asked today to write a function to calculate the number of bits set in a given integer. That is, there is one bit set in 4 (100), but two bits set in 5 (101) .
int CountOfBitsSet(int n) { int count = 0; while (n > 0) { if (n%2 == 1) count++; n = n >> 1; } return count; }The follow up question was the maximum number of times the main loop would..err…loop1. The follow up to that was how I could optimise it. I didn’t know, and it was suggested to me that you could use a lookup table. I agreed that if it was something that was likely to remain in memory for awhile and be used a lot, you could maintain a hash of previously calculated values, but what they were really getting at was a lookup table that is preloaded. That’s a lot of memory, that is for just over 2.1 billion numbers.
Obviously the last follow up question was how you could optimise this ridiculous unhelpful lookup table. I couldn’t think of one, I was too distracted by how ridiculously unhelpful that lookup table would be and just suggested that I wouldn’t do that, I’d just use a populated-as-generated hash.
There’s a term for thinking of the perfect comeback ten minutes too late; is there one for thinking of a good answer to a question a few hours later2?
It’s in Ruby instead of the C# I was being tested in. Since they weren’t testing me in the language so much as problem solving, I’m quite sure it wouldn’t have mattered.
class BitCounting LOOKUPS = {"0"=>0, "1"=>1, "2"=>1, "3"=>2, "4"=>1, "5"=>2, "6"=>2, "7"=>3, "8"=>1, "9"=>2, "a"=>2, "b"=>3, "c"=>2, "d"=>3, "e"=>3, "f"=>4} def self.numBitsSet(n) hex_ver = n.to_s(base=16) count = 0 (0..hex_ver.length-1).each{|digit|count += LOOKUPS[hex_ver[digit]]} count end endMaximum number of iterations through the loop drops to 8, and the lookup table has a negligible footprint.
Bah!
1 31.
2 Apart from too bloody late by half.
-
# Jury duty
In August of 2007 a security guard for a company that provided security for ATM technicians finished his shift early, went through all the procedures for signing in his weapon and keys, left the premises and then allegedly broke and entered an ATM bunker and stole $270K+. The next morning he turned up for work and hour and a half before his shift started, appeared to break certain parts of the procedure for being assigned keys, including taking keys out of the secured area, out of shot of CCTV cameras, before they are audited. Four days later, after a period during the police couldn’t contact him, he was lured into work by his boss with the pretense of a team meeting, and promptly arrested by NSW police detectives from the Liverpool command. He was taken to the station and then proceeded to give a hour-long statement in which he appeared to constantly repeat a number of rehearsed lines. Or maybe he was just repeating the only explicable things, the security procedure he followed, specifically the bit that if it had indeed been followed, would exonerate him.
I know this because I spent the last fortnight as part of the jury. I now know more about the security of ATMs as operated by Linfox Armaguard then most people. Possibly more even than some of the people actually responsible. I know that the electronic security system for the locks has never been tested properly, relying instead on security by obscurity. I know that the system of keys, commercially available iButton devices easily obtainable from the internet. The emulation of these is a project routinely assigned to first year Electrical Engineering students, in Sydney and elsewhere; a fact attested to by a man who holds a Top Secret clearance in Australia, does security consultation work for the Department of Defense and ASIO, is currently doing testing work for international air traffic control – with the aim of simulating bringing down an airplane – a course adviser for the Electrical Engineering department at one of those Sydney universities, a man who in the act of pwning the expert witness from the firm that supplied the security system mentioned that he personally had conducted white hat operations against a security system functionally indistinguishable from that used by the ATM.
I know that the police can and do get a species of target fixation. They’ll focus so much on who they like for the crime that they forget to actually make sure of everything, to cross the T’s and dot the I’s. They’ll not think to go back over footage from the weeks prior to the crime and check the accused’s assertion that all the guards take the keys off camera and into the kitchen prior to the filmed auditing process. They’ll not bother to take a statement from the technician who was at the ATM the day after the robbery and, through confusion at the bank’s Helpdesk, did not realise that the reason the ATM was empty was not because of an official decashing, but a very unofficial one. They won’t take this statement until two years later, on the penultimate day of the trial for the crime. They won’t go to the operators of the security system and thoroughly and completely trash out what has happened, a process that might have eliminated one of the alternative narratives raised by the defense – that of a rogue security technician – and would almost certainly have prevented a security technician having to tell the lawyers during a visit to the crime scene that he can’t explain why the safe even opened since it was in the lock out period when the keys can’t even open the damn thing, only to have to back down the next day when he finds out he is mistaken about when the lock out period starts each night. The Crown prosecutor, for at least twelve hours, thought his entire case had been blown out of the water. This occurred the day after the jury was empaneled and the trial had begun. Brilliant.
As you can probably already tell, we the jury found the accused not guilty. Right up until the last hour or so of the defense summation there was still doubt which way it would go. I had been stressing over the decision, unsure which way to go: I was reasonably sure he had indeed done the crime but I knew I was basing that on some inferences and didn’t want to send a guy to gaol when he might not have done it. The stress was stupid, I knew it was stupid at the time, I knew that if I wasn’t sure I had to go with not guilty, but the knowledge just couldn’t penetrate the outer shell of “I am pretty sure he did it”. But then defense mentions during his summation that some of the inferences I was drawing weren’t just invalid in a jury decision, but completely invalid in reality.
The trial took nine days. Deliberations took twenty minutes. Could have been five, but one of the jury members deliberately voted against the flow so that he could make sure we would still get lunch for the day. Well, also because he thought five minutes might have been a bit unseemly. But the lunch bit also. I had been sure there was going to be hours of circular arguments because half of the jury had spent the entire trial going over irrelevancies in the evidence. In the end though it came down to whether the accused had access to three distinct things. He certainly had access to one, the electronic keys, and everyone else believed he had access to a second. I didn’t and while I stood my ground in a discussion on it, it didn’t matter because nobody in the room could say that they were sure beyond reasonable doubt that he had the third item. Yes, it sounds like Cluedo; The security guard, in the ATM bunker, with the e keys, the keys and the alarm code.
The forewoman – all of twenty-four – was sweating bullets about having to read the verdict. She thought she had to speak directly to the accused. She thought she had to explain why we made the decision we did. No, she just had to say two words to His Honour’s assistant, sit down and then within seconds we were dismissed and away we go. Hoping never to see the accused again, a hope that might be forlorn in the case of the forewoman, because as it turns out, she lives two streets away from him. Even if she does see him, it has to be better than bumping into him on the street as happened for a number of us. In cafes while getting coffee in the morning. You’d walk in, see him and walk back out again because it’s just too awkward to bear.
That’s how I spent the last two weeks. That doesn’t explain the preceding seven weeks, but that time is lost.
-
# Today, we are all stateless
