php 32位整数溢出问题

Question

有以下c函数用于将一个字符串生成一个hash码，返回类型为unsigned long类型.
static unsigned long
hash_string (const void *key)
{
  const char *p = (const char *)key;
  unsigned int h = *p;
  
  if (h)
    for (p += 1; *p != '\0'; p++)
      h = (h << 5) - h + *p;
  
  return h;
}
我现在要将以上代码移植为php的函数,如下:function hash_string($str)
        {
                $length = strlen($str);
                $h = ord($str[0]);
                if($length > 0)
                    for($i = 1; $i < $length; ++$i)
                    {
                        $h = ($h << 5) - $h + ord($str[$i]);
                    }
                return sprintf("%u", $h);
        }
但该php函数面临32位整数溢出的问题，在c语言中，不断左移5位的话，溢出的位会被抛弃，也就是无论怎样移位，都会卡在32位范围内;
但php则会一直扩大下去以至于超出32位的范围.我想问的是，如何才能让php保持在32位的范围内操作一个数呢？

Answer 1

将处理的变量,强制类型转换成int型.
int 是4字节的.

Answer 2

$h = (($h << 5) & 0xffffffff) - $h + ord($str[$i]);

Answer 3

这个思路非常不错，让我耳目一新，不过结果还是不正确:        function hash_string($str)
        {
                $length = strlen($str);
                $h = ord($str[0]);
                if($length > 0)
                    for($i = 1; $i < $length; ++$i)
                        $h = (($h << 5) & 0x00ffffffff) - $h + ord($str[$i]);
                return sprintf("%u", $h);
        }        echo hash_string("http://topic.csdn.net/u/20100428/14/283A1AD5-46E0-4A28-92D5-547D994074BF.html")."\n";
计算这个链接得到的hash值为 2147483648， 不用问这个结果一看就是溢出导致的！

Answer 4

#include <stdio.h>
unsigned long hash_string (const void *key);void main(void) {
  printf("%u", hash_string("http://topic.csdn.net/u/20100428/14/283A1AD5-46E0-4A28-92D5-547D994074BF.html"));
}
unsigned long
hash_string (const void *key)
{
  const char *p = (const char *)key;
  unsigned int h = *p;
  
  if (h)
    for (p += 1; *p != '\0'; p++)
      h = (h << 5) - h + *p;
  
  return h;
}
输出：962577676function hash_string($str)
        {
                $length = strlen($str);
                $h = ord($str[0]);
                if($length > 0)
                    for($i = 1; $i < $length; ++$i)
                        $h = (($h << 5) & 0xffffffff) - $h + ord($str[$i]);
                return sprintf("%u", $h);
        }        echo hash_string("http://topic.csdn.net/u/20100428/14/283A1AD5-46E0-4A28-92D5-547D994074BF.html")."\n";
输出：962577676有什么不对吗？

Answer 5

奇怪我这里依然是2147483648
我这里是在linux下，php版本为5.1.6.你是在什么平台呢？

Answer 6

windows 2003 + IIS6 + PHP 5.2.6

Answer 7

我试了，在windows下也能得到正确的结果，但在linux下还是出现这个问题

Answer 8

先不计算，逐字节对比,看看是哪里的问题
function hash_string($str) {
                $length = strlen($str);
  for($i-0; $i<$length; $i++) {
    $h = ord($str[$i]);
    printf("%d %d %d\n", $i, $h, ($h<<5));
  }
/*
                $h = ord($str[0]);
                if($length > 0)
                    for($i = 1; $i < $length; ++$i)
                        $h = (($h << 5) & 0xffffffff) - $h + ord($str[$i]);
                return sprintf("%u", $h);
*/
}echo hash_string("http://topic.csdn.net/u/20100428/14/283A1AD5-46E0-4A28-92D5-547D994074BF.html")."\n";

Answer 9

照您的意思进行了更改:function hash_string($str)
        {
                $length = strlen($str);
                $h = ord($str[0]);
                if($length > 0)
                    for($i = 1; $i < $length; ++$i)
{
                        $h = (($h << 5) & 0xffffffff) - $h + ord($str[$i]);
printf("%d %d\n", $i, $h);
}
                return sprintf("%u", $h);
        }        echo hash_string("http://topic.csdn.net/u/20100428/14/283A1AD5-46E0-4A28-92D5-547D994074BF.html")."\n";
每次打印$h的值:
windows下:
1 3340
2 103656
3 3213448
4 99616946
5 -1206841923
6 1242606098
7 -133916510
8 143555597
9 155256323
10 517978822
11 -1122525603
12 -438555279
13 -710311662
14 -544824927
15 290296547
16 409258475
17 -197889117
18 -1839595221
19 -1192876902
20 1675521818
...linux下:
1 3340
2 103656
3 3213448
4 99616946
5 -1206841923
6 1242606098
7 -133916510
8 143555597
9 155256323
10 517978822
11 -1122525603
12 -438555279
13 -710311662
14 -544824927
15 290296547
16 409258475
17 -197889117
18 -1839595221
19 -1192876902
20 -2147483648
...计算到第二十个字符的时候，两者有了差别,windows上的看似正常，
但linux下的则像是个整数溢出了的值,负整数溢出.

Answer 10

测试：
$n = -1192876902;
printf("n<<5 :%032s %u<br>", decbin($n<<5), $n<<5);
printf("n原值:%032s %u<br>", decbin($n), $n);
printf("t内值:%032s %u<br>", decbin(ord('t')), ord('t'));
printf("结果: %032s %u<br>", decbin(($n<<5)-$n+ord('t')), ($n<<5)-$n+ord('t'));
printf("%032s<br>", decbin(-2147483648));n<<5 :00011100110001001001001101000000 482644800
n原值:10111000111001100010010010011010 3102090394
t内值:00000000000000000000000001110100 116
结果: 01100011110111100110111100011010 1675521818
10000000000000000000000000000000得到 -2147483648 显然是错误的
在调试上述测试代码时，曾有一次出现结果 2147483647 即二进制 01111111111111111111111111111111
仅出现一次，原因不明。请其他使用Linux系统的朋友测试一下

Answer 11

发现问题所在了，是php版本问题，我将系统中的php升级为5.3.2，这个问题不存在了！

Answer 12

php下不会溢出，移位完求个余就可以了，没必要又与又加的这么麻烦。