# 快速搜索在相同偏移的两个int中的某些小点心(c，微观化)[英] Fast search of some nibbles in two ints at same offset (C, microoptimisation)

### 问题描述

```bit offset:   12345678
first int:  0x3d542783     first pair of  0x2    second:   0xd
second int: 0x486378d9      nibbles:      0x7      pair:   0x8
^  ^
```

so，对于给定的两个int，问题是:它们是否包含同一偏移的这些对nibbles中的任何一对.

```static inline int nibble_check (uint32_t A, uint32_t B)
__attribute__((always_inline))
{
int i;
for(i=0;i<8;i++)

if(  ( ( (A&0xf) ==0xD) && ( (B&0xf) ==0x8) )     // first pair
|| ( ( (A&0xf) ==0x2) && ( (B&0xf) ==0x7) )  )  // second pair
return 1; // nibbles found
else {
A>>=4;
B>>=4;
}

}
```

```#define douburu_nibble_check(A,B) (nibble_check(A,B) || nibble_check(A>>2, B>>2) )
```

## 推荐答案

```(x - 0x01010101) & ~x & 0x80808080
```

```static inline int nibble_check(uint32_t A, uint32_t B)
{
uint32_t tmp1, tmp2;

tmp1 = (A ^ 0x22222222) | (B ^ 0x77777777);
tmp2 = (A ^ 0xdddddddd) | (B ^ 0x88888888);

return !!(((tmp1 - 0x11111111) & ~tmp1 & 0x88888888) |
((tmp2 - 0x11111111) & ~tmp2 & 0x88888888));
}
```

## 其他推荐答案

``` /* Look for 0x2 in either nibble - hits on 0x02, 0x20, 0x22 */
char table_0x2[] = {
0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* 0x02 */
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* 0x20, 0x22 */
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
};

char table_0x7[] = { fill this in };
char table_0xd[] = { fill this in };
char table_0x8[] = { fill this in };

int nibble_check (uint32_t A, uint32_t B)
{

int i;

for (i = 0; i < 4; i++) {
if ((table_0x2[A & 0xff] && table_0x7[B & 0xff]) ||
(table_0xd[A & 0xff] && table_0x8[B & 0xff])) {
/*
* check to see if the A&B hits are in corresponding
* nibbles - return 1 or break
*/
}

A = A >> 8;
B = B >> 8;

}
return 0;
}
```

``` /* 16 bit tables - upper 8 bits are A, lower 8 bits are B */
/* for 0x02, 0x07 */
char *table_2_7;
/* for 0x0d, 0x08 */
char *table_d_8;

void init(void)
{
int i;
int j;

/* error checking eliminated for brevity */
table_2_7 = malloc(64 * 1024);
table_d_8 = malloc(64 * 1024);

memset(table_2_7, 0, 64 * 1024);
memset(table_d_8, 0, 64 * 1024);

for (i = 0 ; i < 16; i++) {
for (j = 0 ; j < 16; j++) {
table_2_7[(i << 12)   | (0x2 << 8)  | (j << 4)   | (0x7 << 0)] = 1;
table_2_7[(0x2 << 12) | (i << 8)    | (0x7 << 4) | (j << 0)] = 1;

table_d_8[(i << 12)   | (0xd << 8)  | (j << 4)    | (0x8 << 0)] = 1;
table_d_8[(0xd << 12) | (i << 8)    | (0x8 << 4) | (j << 0)] = 1;
}
}

}

int nibble_check(uint32_t A, uint32_t B)
{
int i;

for (i = 0; i < 4; i++) {
if (table_2_7[ ((A & 0xff) << 8) | (B & 0xff) ] ||
table_d_8[ ((A & 0xff) << 8) | (B & 0xff) ]) {
return 1;
}

A = A >> 8;
B = B >> 8;

}
return 0;
}
```

## 其他推荐答案

```if( ( ((A & 0x0000000F) == 0x0000000D) && ((B & 0x0000000F) == 0x00000008) )
|| ( ((A & 0x000000F0) == 0x000000D0) && ((B & 0x000000F0) == 0x00000080) )
|| ( ((A & 0x00000F00) == 0x00000D00) && ((B & 0x00000F00) == 0x00000800) )
|| ( ((A & 0x0000F000) == 0x0000D000) && ((B & 0x0000F000) == 0x00008000) )
// etc
// Then repeat with 2 & 7
```

.
```bool result = false;
result |= ( ((A & 0x0000000F) == 0x0000000D) && ((B & 0x0000000F) == 0x00000008) )
result |= ( ((A & 0x000000F0) == 0x000000D0) && ((B & 0x000000F0) == 0x00000080) )
result |= ( ((A & 0x00000F00) == 0x00000D00) && ((B & 0x00000F00) == 0x00000800) )
result |= ( ((A & 0x0000F000) == 0x0000D000) && ((B & 0x0000F000) == 0x00008000) )
// etc
return result;
```