Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

A neat XOR trick

mattkeeter.com

Post reply on HN
Print view View original

111–120 of 181 posts

Re: A neat XOR trick

#111

Post by thomasahle »

bsza wrote: post #104
thomasahle wrote: post #100

Earlier quoted context omitted.

You could imagine a much larger character set though. For example you might be interested in a sliding window of unique words instead.

Yes, but then the last algorithm runs in the same time as the one before it. Using xor here really only gives you a constant factor improvement (which is still nice!). Reminds me of the problem “find the only missing number in a scrambled list of 1..n”. You can get an “O(n)” solution using xor, but once bit size becomes a concern, there are less hacky solutions that are just as fast.

"Bit tricks" are worth a factor `log n`. Let me explain: If you have an array of `n` integers in {0,1}, and you want to count the number of 1s, you need `n` time. But if you have an array of `n` bits, with bit level operations you can do `n/W` time, where `W` is your word size. We often have W=32, 64 or 256 on some architectures, but you may still argue it's just a constant.

The thing is that we usually saw you have random access to all of your input data in constant time. But if your input size is `n`, your pointer size must be `log n`. So for standard algorithm analysis to work, you need to allow a word size of at least `log n`.

Re: A neat XOR trick

#112

Post by pklausler »

adrian_b wrote: post #28
moloch-hai wrote: post #17

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.

It is good to remember that the instruction POPCNT was introduced for the first time in the instruction set of a computer by Alan Turing, already in 1949, in Ferranti Mark I (as "sideways add"). Unfortunately few other computers have included it before Cray 1, which made it well known, under the current name.

We had it on the CDC 6600 in 1963 as 'Bi NXj' if I remember rightly.

Re: A neat XOR trick

#113

Post by mjburgess »

aarestad wrote: post #108
mjburgess wrote: post #106

I may be missing something, but isnt the obvious answer just to scan-and-compare 4 chars/time ? (Noting that != is XOR). int main(void) { char *c = 0, *data = "nznrnfrfntjfmvfwmzdfjlvtqnbhcprsg"; for ( c = data; !((c[1] != c[0]) && ((c[2] != c[1]) && (c[2] != c[0])) && ((c[3] != c[2]) && (c[3] != c[1]) && (c[3] != c[0]))); c++ ); printf("%ld", c-data+4); }

Sure, but now do 11 at a time with a similar algorithm (which was part 2 of the problem).

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.

Re: A neat XOR trick

#114

Post by segmondy »

dukoid wrote: post #53

FTR: This can be done with "only" two loops (opposed to the "naive" 3 in the article) -- without any extra data structures. It's sufficient to keep track of how many characters have been unique so far. For each "new" character, check whether it's different from all of them. If so, increase count. Otherwise, reset count to the distance to the match. def main(): count = 1 for i in range(1, len(SIGNAL)): for j in range(…

The article started with 3 loops, took it down to 2 then one. Why are you talking about 2 loops?

Re: A neat XOR trick

#115

Post by dukoid »

segmondy wrote: post #114
dukoid wrote: post #53

FTR: This can be done with "only" two loops (opposed to the "naive" 3 in the article) -- without any extra data structures. It's sufficient to keep track of how many characters have been unique so far. For each "new" character, check whether it's different from all of them. If so, increase count. Otherwise, reset count to the distance to the match. def main(): count = 1 for i in range(1, len(SIGNAL)): for j in range(…

The article started with 3 loops, took it down to 2 then one. Why are you talking about 2 loops?

The article took it down to 2 by adding an extra hashtable. It's possible to go down to 2 without using an extra data structure.

Re: A neat XOR trick

#116

Post by leipert »

mjburgess wrote: post #106

I may be missing something, but isnt the obvious answer just to scan-and-compare 4 chars/time ? (Noting that != is XOR). int main(void) { char *c = 0, *data = "nznrnfrfntjfmvfwmzdfjlvtqnbhcprsg"; for ( c = data; !((c[1] != c[0]) && ((c[2] != c[1]) && (c[2] != c[0])) && ((c[3] != c[2]) && (c[3] != c[1]) && (c[3] != c[0]))); c++ ); printf("%ld", c-data+4); }

2nd part is a window of length 14.

Re: A neat XOR trick

#117

Post by twic »

One small thing:

        // Turn on bits as they enter the window
        set ^= 1 = window_size {
            set ^= 1
"turn on" and "turn off" actually mean "flip", right? Each bit is not a present/not present flag, it's the parity of the count of number of occurrences. Which still works, because of the "counting how many characters appear an odd number of times in a window" thing.

Re: A neat XOR trick

#118

Post by chasil »

boredumb wrote: post #61

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.

This is vaguely reminiscent of the xor swap procedure, although it seems more practical.

https://en.wikipedia.org/wiki/XOR_swap_algorithm

Re: A neat XOR trick

#119

Post by WorldMaker »

robinhouston wrote: post #73
jandrese wrote: post #72

Earlier quoted context omitted.

The example code in the article left out the lookup table to convert each character into a single bit representation. All the tricky xor and popcount stuff could have been a 26 byte array just as easily and been O(n).

There's no lookup table. The example code in the article does the conversion using this expression: 1

Yes, for some additional explanation for those that might use it, that's "ASCII math": it assumes all lowercase ASCII Latin letters (which most Unicode encodings including UTF-8 and UTF-32 inherit). ASCII was intentionally designed so that the lowercase letters a-z are in English alphabet order and so subtracting 'a' from the letter gives you an alphabet position number from 0-25. (The same applies in ASCII for the upper case range A-Z and the numerical range 0-9, though doing math between ranges is less fun.)

Then you've just got a standard single 1 left shifted 0-25 positions. (So 'a' is 1 and 'z' is 1*2^25.)

Re: A neat XOR trick

#120

Post by dentalperson »

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?
Post reply on HN