2017-10-29 12:46


  • random
  • as
  • 函数
  • it
  • lines

Problem Description
Carelessly designed cryptographic primitives leave your secret as bared as plain text. It is not a surprise that seemingly "random" hash functions are weak. Consider the function of the following form:

unsigned int hash(unsigned int x) {
x += 0x327b7473u;
x &= 0xffffafffu;
x ^= 0x90283712u;
x |= 0x00300000u;
x += 0x89129723u;
x ^= 0x464726ccu;
x &= 0xfffff8ffu;
return x;

The function maps an integer to another integer and intends to make the result random. All statements are of the form: x (some operator) (some number). Possible operators are: add (+=), subtract (-=), bitwise-and (&=), bitwise-xor (^=), and bitwise-or (|=). Due to the nature of fixed size integer, there is an implicit modulo 4294967296 operation after each statement.

However, it is a rather weak hash function from a cryptographic point of view. To demonstrate its weakness, you are requested to find an input x that maximizes the output.

In this example the best x is 1841992591 and the maximum output is 4292342015.

The first line contains an integer T, denoting the number of the test cases.

Each test case begins with a non-negative integer N, the number of operations in the hash function. 0<=N<=40.

Then follows N lines, each describing an operation. Each line contains an operator and an 8-digit hexadecimal number.

For each test case, output the maximum output in decimal format.

Sample Input
+= 327b7473
&= ffffafff
^= 90283712
|= 00300000
+= 89129723
^= 464726cc
&= fffff8ff
-= 00000001

Sample Output

  • 点赞
  • 回答
  • 收藏
  • 复制链接分享