位操作黑客：交错位的明显途径

本文介绍了位操作黑客：交错位的明显途径的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述 我有兴趣在这个问题上can someone explain to me how this works with an example?for example if we have x = 100101 and y = 010101, what will be result? 解决方案 Bit interleaving essentially takes two n bit input numbers and produces one 2n bit output number that alternately takes bits from the two input numbers. That is, bits from one number goes into the odd indices, and bits from the other goes into the even indices.So for your specific example:x = 100101 = 1 0 0 1 0 1y = 010101 = 0 1 0 1 0 1interleaved = 011000110011Here we use the convention that bits from x goes into the even indices (0, 2, 4...) and bits from y goes into the odd indices (1, 3, 5...). That is, bit interleaving is not a commutative operation; interleave(x, y) is generally not equal to interleave(y, x).You can also generalize the bit interleaving operation to involve more than just 2 numbers.Bit-interleaved numbers exhibit structural properties that can be taken advantage of in many important spatial algorithms/data structures.See alsoWikipedia/Z-order (curve)aka Morton-Order/Morton codeRelated questionsHow to compute a 3D Morton number (interleave the bits of 3 ints)How to de-interleave bits (UnMortonizing?)"Obvious" algorithmThe algorithm essentially goes through every bits of the input numbers, checking if it's 1 or 0 with bitwise-and, combining the two bits with bitwise-or, and concatenating them together with proper shifts.To understand how the bits are rearranged, just work on a simple 4-bit example. Here xi denotes the i-th (0-based) bit of x.x = x3 x2 x1 x0y = y3 y2 y1 y0 Mapping:z = y3 x3 y2 x2 y1 x1 y0 x0 x[i] --> z[i+i] z7 z6 z5 z4 z3 z2 z1 z0 y[i] --> y[i+i+1]Once you convinced yourself that the mapping pattern is correct, implementing it is simply a matter of understanding how bitwise operations are performed.Here's the algorithm rewritten in Java for clarity (see also on ideone.com): int x = Integer.parseInt("100101", 2); int y = Integer.parseInt("010101", 2); int z = 0; for (int i = 0; i < Integer.SIZE; i++) { int x_masked_i = (x & (1 << i)); int y_masked_i = (y & (1 << i)); z |= (x_masked_i << i); z |= (y_masked_i << (i + 1)); } System.out.println(Integer.toBinaryString(z)); // prints "11000110011"See alsoWikipedia/Bitwise operations 这篇关于位操作黑客：交错位的明显途径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！