141–150 of 181 posts
Something about seeing fun bit tricks solving higher level problems is exciting. As someone who writes higher level software in general using golang/rust/python to solve "boring business" problems, seeing someone using XORs to accomplish something feels like leaving my house and going camping for the weekend.
Right? Things like fast inverse square root feel like total black magic.
Earlier quoted context omitted.
legend say that popcnt was the "NSA" instruction, was heavily used for cryptographic analysis and that was kept out of common instruction sets for a long time to give NSA an advantage. It is probably just a legend though.
The usefulness of popcnt, et al, in cryptography was known at least as far back as Alan Turing. It wasn't 'kept out of' ISAs, if for no other reason than not all computer manufacturers were (are) American, so the NSA wouldn't have had much leverage to keep, say, Ferranti or Hitachi from including it in their computers. The legend you're probably misremembering is the one where the NSA approached Seymor Cray at CDC wh…
Ok. Why??????????????
@gpderetta is correct at least in quoting hacker's delight where it was also said to be rumoured the NSA wanted popcount but it was unclear to HD's author why they wanted it.
Earlier quoted context omitted.
I've just submitted in order to see the second part, which just says "now look for 14 unique". I dont see the problem here, if you want a notation to express it, a macro for something like, 0 != 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13 1 != 0, 2, 3, 4, 5, 6, 7, ... is straightforward, and could be parameterised on the window size.
That's fine, but it's O(n) in the window size whereas the xor trick is O(1).
There shouldnt be a loop over the window size in solutions to this (particular) problem
I've seen this use of constants inside big O notation in leetcode and 'informal' discussions. Is it pedantic to say that O(NM) == O(N) if M is a constant (in this case since it's bound by 26)? Or is this the current and expected usage?
It's correct to omit constants from big O, but in the article W is a distinct input variable so the usage is valid. The size of the window W is bound by N, not a constant 26.
Normally for a search algorithm the size of the alphabet is assumed to be constant.
Earlier quoted context omitted.
The usefulness of popcnt, et al, in cryptography was known at least as far back as Alan Turing. It wasn't 'kept out of' ISAs, if for no other reason than not all computer manufacturers were (are) American, so the NSA wouldn't have had much leverage to keep, say, Ferranti or Hitachi from including it in their computers. The legend you're probably misremembering is the one where the NSA approached Seymor Cray at CDC wh…
> The usefulness of popcnt, et al, in cryptography was known at least as far back as Alan Turing Ok. Why?????????????? @gpderetta is correct at least in quoting hacker's delight where it was also said to be rumoured the NSA wanted popcount but it was unclear to HD's author why they wanted it.
Cryptography has advanced since then - and I'm not an expert - but there may still be statistical weaknesses that could be found by counting bits?
Earlier quoted context omitted.
The usefulness of popcnt, et al, in cryptography was known at least as far back as Alan Turing. It wasn't 'kept out of' ISAs, if for no other reason than not all computer manufacturers were (are) American, so the NSA wouldn't have had much leverage to keep, say, Ferranti or Hitachi from including it in their computers. The legend you're probably misremembering is the one where the NSA approached Seymor Cray at CDC wh…
> The usefulness of popcnt, et al, in cryptography was known at least as far back as Alan Turing Ok. Why?????????????? @gpderetta is correct at least in quoting hacker's delight where it was also said to be rumoured the NSA wanted popcount but it was unclear to HD's author why they wanted it.
The moral is that POPCNT is critical to zillions of massive optimizations, and omitting it from base instruction sets, as has been done over and over and then later corrected, each time at great expense, is extremely foolish. The latest offender was RISC-V, but the overwhelming majority of x86 code is still compiled to a target version lacking it.
>RISC-V Doesn't B have a POPCNT? B is mandatory in RVA22.
Can someone explain the 1 “ fn run(s: &[char], window_size: usize) -> usize { let mut set = 0u32; for i in 0..s.len() { // Turn on bits as they enter the window set ^= 1 // Turn off bits as they leave the window if i >= window_size { set ^= 1 } “
'1 'Stuff' there is just any expression (to understand separately) that evaluates to the number of positions to shift; ` >`). In brief `(s[i - window_size] as u32 - 'a' as u32)` is finding the character that just left the window on the left, represented as a number, starting from 'a' as 0 so that all 26 fit inside 32 bit positions.
This seems a bit overcomplicated to me. Using a bitmap to track letters you've seen is a great idea. But the parity and counting gives me a headache. How about you start with a zero-size window at the start of the string, then iteratively try to grow it by moving the end forward until it's long enough, and if the character added would be a duplicate, moving the start forward until it's no longer a duplicate? Sort of…
I had to make zero changes, it appears to work.