Skip to main content
added 155 characters in body
Source Link
D.W.
  • 165.6k
  • 21
  • 230
  • 490

You can sort the five items and simultaneously check for duplicates without any comparisons on some processors: Assume a processor has a fast instruction which determines the position of the highest bit set, and a fast instruction calculating a number with only the n-th bit set.

Let bit (n) be the number with exactly the n-th bit set. Let highest_bit (x) be the number of the highest bit that is set in the number x, with an unspecified value if x = 0. Let x ^ y be the exclusive-or of x and y.

Given are five numbers a, b, c, d and e, each from 0 to 51, representing the five cards in the hand.

Let x = bit (a) ^ bit (b) ^ bit (c) ^ bit (d) ^ bit (e).

Let A = highest_bit (x), change x to x ^ bit (A).

Let B = highest_bit (x), change x to x ^ bit (B).

Let C = highest_bit (x), change x to x ^ bit (C).

Let D = highest_bit (x), change x to x ^ bit (D).

Let E = highest_bit (x).

If x = 0 then there were duplicates in the numbes a, b, c, d, and e. Otherwise, use A * bit (24) + B * bit (18) + C * bit (12) + D * bit (6) + E as the encoding of the hand, and letwhere A, B, C, D and E by theare defined valueas above. This encodes a hand as a 30-bit string, while doing the sorting in a very efficient way.

You can sort the five items and simultaneously check for duplicates without any comparisons on some processors: Assume a processor has a fast instruction which determines the position of the highest bit set, and a fast instruction calculating a number with only the n-th bit set.

Let bit (n) be the number with exactly the n-th bit set. Let highest_bit (x) be the number of the highest bit that is set in the number x, with an unspecified value if x = 0. Let x ^ y be the exclusive-or of x and y.

Given are five numbers a, b, c, d and e, each from 0 to 51.

Let x = bit (a) ^ bit (b) ^ bit (c) ^ bit (d) ^ bit (e).

Let A = highest_bit (x), change x to x ^ bit (A).

Let B = highest_bit (x), change x to x ^ bit (B).

Let C = highest_bit (x), change x to x ^ bit (C).

Let D = highest_bit (x), change x to x ^ bit (D).

Let E = highest_bit (x).

If x = 0 then there were duplicates in the numbes a, b, c, d, and e. Otherwise, use A * bit (24) + B * bit (18) + C * bit (12) + D * bit (6) + E, and let A, B, C, D and E by the defined value.

You can sort the five items and simultaneously check for duplicates without any comparisons on some processors: Assume a processor has a fast instruction which determines the position of the highest bit set, and a fast instruction calculating a number with only the n-th bit set.

Let bit (n) be the number with exactly the n-th bit set. Let highest_bit (x) be the number of the highest bit that is set in the number x, with an unspecified value if x = 0. Let x ^ y be the exclusive-or of x and y.

Given are five numbers a, b, c, d and e, each from 0 to 51, representing the five cards in the hand.

Let x = bit (a) ^ bit (b) ^ bit (c) ^ bit (d) ^ bit (e).

Let A = highest_bit (x), change x to x ^ bit (A).

Let B = highest_bit (x), change x to x ^ bit (B).

Let C = highest_bit (x), change x to x ^ bit (C).

Let D = highest_bit (x), change x to x ^ bit (D).

Let E = highest_bit (x).

If x = 0 then there were duplicates in the numbes a, b, c, d, and e. Otherwise, use A * bit (24) + B * bit (18) + C * bit (12) + D * bit (6) + E as the encoding of the hand, where A, B, C, D and E are defined as above. This encodes a hand as a 30-bit string, while doing the sorting in a very efficient way.

Source Link
gnasher729
  • 31.6k
  • 35
  • 55

You can sort the five items and simultaneously check for duplicates without any comparisons on some processors: Assume a processor has a fast instruction which determines the position of the highest bit set, and a fast instruction calculating a number with only the n-th bit set.

Let bit (n) be the number with exactly the n-th bit set. Let highest_bit (x) be the number of the highest bit that is set in the number x, with an unspecified value if x = 0. Let x ^ y be the exclusive-or of x and y.

Given are five numbers a, b, c, d and e, each from 0 to 51.

Let x = bit (a) ^ bit (b) ^ bit (c) ^ bit (d) ^ bit (e).

Let A = highest_bit (x), change x to x ^ bit (A).

Let B = highest_bit (x), change x to x ^ bit (B).

Let C = highest_bit (x), change x to x ^ bit (C).

Let D = highest_bit (x), change x to x ^ bit (D).

Let E = highest_bit (x).

If x = 0 then there were duplicates in the numbes a, b, c, d, and e. Otherwise, use A * bit (24) + B * bit (18) + C * bit (12) + D * bit (6) + E, and let A, B, C, D and E by the defined value.