Can someone explain the 1 << stuff? I’m very new to bit fiddling but I did follow the blog.
“ 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 << (s[i] as u32 - 'a' as u32);
// Turn off bits as they leave the window
if i >= window_size {
set ^= 1 << (s[i - window_size] as u32 - 'a' as u32);
}
// Check the current window and see if we're done
if set.count_ones() as usize == window_size {
return i + 1;
}
}
panic!("No unique window found");
The "stuff" assigns an integer value to the char. 'b' - 'a' = 1, for example. This assigns each char a unique integer value. By shifting 1 up that many times, you assign a unique bit position to each char.
For those new to bitshifting, here are the results of the "stuff" operation that @dahfizz describes:
'a' - 'a' = 0, so take 1 and shift it left 0 times:
00000000000000000000000000000001 = 'a'
'b' - 'a' = 1, so take 1 and shift it left 1 time:
00000000000000000000000000000010 = 'b'
'c' - 'a' = 2, so take 1 and shift it left 2 times:
00000000000000000000000000000100 = 'c'
(I'm not sure why the post's author chose to use 10000000000000000000000000000000 as their example for 'a' rather than the above which IIUC is how the code actually works.)
'1 << stuff' = 'bit shift left 1 by stuff many positions'. Say you have a byte, 8 bits, '1' is 00000001 - if we shift it left 3 bits we have 00001000 (8).
'Stuff' there is just any expression (to understand separately) that evaluates to the number of positions to shift; `<<` is the operator for bit-shifting (left, cf. `>>`).
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.
“ 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 << (s[i] as u32 - 'a' as u32);
} “