| 网站首页 | 业界新闻 | 小组 | 交易 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
共有 279 人关注过本帖, 1 人收藏
标题:求解:90个数字哈希表与神秘数字
只看楼主 加入收藏
G笨鸟先飞
Rank: 1
等 级:新手上路
帖 子:4
专家分:0
注 册:2019-9-23
  问题点数:0  回复次数:5   
求解:90个数字哈希表与神秘数字
求解:90个数字哈希表与神秘数字
unsinged int v;  // 整数
int r;           // 运算结果
static const int MultiplyDeBruijnBitPosition[32] ={
  0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
  31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
};
r = MultiplyDeBruijnBitPosition[((uint32_t)((v & -v) * 0x077CB531U)) >> 27];

 

64位的如下: 神秘数字:0x3f79d71b4cb0a89UL
64个数字的哈希表为:
const char g_math_64[] ={0,1,48,2,57,49,28,3,61,58,50,42,38,29,17,4,62,55,59,36,53,51,
43,22,45,39,33,30,24,18,12,5,63,47,56,27,60,41,37,16,54,35,52,21,44,32,23,11,46,26,40,
15,34,20,31,10,25,14,19,9,13,8,7,6};
求log2的算法:
#define LOG2_64(v) g_math_64[(uint64_t)((v& -v) * 0x3f79d71b4cb0a89UL) >> 58]

 
如何写出90个数字的哈希表?
90位数字的神秘数字是多少?



请指教!谢了


[此贴子已经被作者于2019-9-24 19:22编辑过]

搜索更多相关主题的帖子: int 数字 const define 哈希表 
2019-09-24 18:23
自学的数学
Rank: 12Rank: 12Rank: 12
等 级:贵宾
威 望:27
帖 子:748
专家分:3171
注 册:2017-11-15
  得分:0 
关于哈希表,有些人不明白,在此做下说明 :
    散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。
    给定表M,存在函数f(key),对任意给定的关键字值key,代入函数后若能得到包含该关键字的记录在表中的地址,则称表M为哈希(Hash)表,函数f(key)为哈希(Hash) 函数。
    若关键字为k,则其值存放在f(k)的存储位置上。由此,不需比较便可直接取得所查记录。称这个对应关系f为散列函数,按这个思想建立的表为散列表。
    对不同的关键字可能得到同一散列地址,即k1≠k2,而f(k1)=f(k2),这种现象称为冲突(英语:Collision)。具有相同函数值的关键字对该散列函数来说称做同义词。综上所述,根据散列函数f(k)和处理冲突的方法将一组关键字映射到一个有限的连续的地址集(区间)上,并以关键字在地址集中的“像”作为记录在表中的存储位置,这种表便称为散列表,这一映射过程称为散列造表或散列,所得的存储位置称散列地址。
    若对于关键字集合中的任一个关键字,经散列函数映象到地址集合中任何一个地址的概率是相等的,则称此类散列函数为均匀散列函数(Uniform Hash function),这就是使关键字经过散列函数得到一个“随机的地址”,从而减少冲突。
2019-09-24 20:47
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:328
帖 子:6802
专家分:39514
注 册:2011-1-18
  得分:0 
1. 若是哈希表的话,你想怎么写就怎么写,有冲突也无所谓,hash并不存在唯一的写法
2. 你的代码是求一个“二进制数”尾部“零”的个数,与“hash”无关,顶多可以叫做“map”。下次别该说明的不说而乱扯不相干的名词
3. 90位数字你准备用什么类型表达?uint64_t 才64位。
看这篇文章吧 https://,里面有个 128位 的
const char g_math_128[] ={0,1,101,2,116,102,60,3,124,117,103,94,82,61,33,4,125,121,118,87,111,104,95,53,90,83,
69,62,48,34,20,5,126,114,122,80,119,109,88,46,112,107,105,73,96,75,54,26,98,91,84,66,
77,70,63,39,56,49,42,35,28,21,14,6,127,100,115,59,123,93,81,32,120,86,110,52,89,68,47,
19,113,79,108,45,106,72,74,25,97,65,76,38,55,41,27,13,99,58,92,31,85,51,67,18,78,44,71,
24,64,37,40,12,57,30,50,17,43,23,36,11,29,16,22,10,15,9,8,7};

#define LOG2_128(v) g_math_128[(__uint128_t)((v) * 0x01fdf3d78edd3970d9ab464c582a5091) >> 121]


2019-09-25 09:05
G笨鸟先飞
Rank: 1
等 级:新手上路
帖 子:4
专家分:0
注 册:2019-9-23
  得分:0 
谢谢二位版主的回复!
为什么菜鸟我想发这贴子?因为不懂。。。。。。

以下是国际象棋引擎作者自己介绍他写的引擎情况:
# Ethereal

Ethereal is a UCI-compliant chess engine. It uses the traditional alpha-beta framework in addition to a variety of pruning, reduction, extension, and other improvements. Some of those improvements include Static Null Move Pruning, Null Move Pruning, Node Razoring, Depth base Futility Pruning, Best-Case Delta Pruning, Current-Move Delta Pruning, Late Move Reductions, Check extensions, and the use of various Transposition Tables. Ethereal generates moves using the Fancy Magic BitBoard technique, but also uses a redundant 64-length array to store pieces for easier lookup. Ethereal is an original engine aside from the Piece Square Tables (currently using Toga II's tables). It is greatly influenced from Crafty, Stockfish, TSCP, MadChess, and Fruit. Ethereal is a hobby project, but more importantly it is an active resume.

# Elo Progression ( Ethereal7.33 and onward )

| Version |  Elo |
| ------: | ---: |
| v7.33   |  2154|
| v7.40   |  2172|
| v7.42   |  2189|
| v7.49   |  2196|
| v7.55   |  2210|
| v7.57   |  2247|
| v7.58   |  2275|
| v7.60   |  2453|
| v7.61   |  2482|
| v7.65*  |  2503|
| v7.69   |  2532|
| v7.70   |  2549|

# Development

As of now, I am the sole contributor to the project. However, I will happily review any Pull Requests and consider merging them into the project. The License on this project allows any individual to use, modify, and release my code and any derivatives made using my code. For any questions or comments, feel free to contact me at <Andrew@Grantnet.us>


作者编写的引擎用新的位棋盘技术很值得学习。我想将其引用到中国象棋引擎中。。。。。。
以下是作者引擎中一段代码
#include <stdint.h>
#include <assert.h>

#include "bitboards.h"
#include "bitutils.h"


int LsbLookupTable[64] = {
    0, 47, 1, 56, 48, 27,  2, 60,
   57, 49, 41, 37, 28, 16,  3, 61,
   54, 58, 35, 52, 50, 42, 21, 44,
   38, 32, 29, 23, 17, 11,  4, 62,
   46, 55, 26, 59, 40, 36, 15, 53,
   34, 51, 20, 43, 31, 22, 10, 45,
   25, 39, 14, 33, 19, 30,  9, 24,
   13, 18,  8, 12,  7,  6,  5, 63
};
  
/**
 * Count the number of set bits in a given 64-bit Integer
 *
 * @param   bb  BitBoard to count set bits in
 * @return      Count of all set bits in bb
 *计算设置位的数量在一个给定的64位整数
  *
  * @param bb位棋盘数套位
  * @return计数设置位的bb

 */
int countSetBits(uint64_t bb){
    int count = 0;
   
    while(bb){
        bb ^= (1ull << getLSB(bb));
        count += 1;
    }
   
    return count;
}

/**
 * Fill an array with the bit indexes of all set bits
 * in a given 64-bit Integer. Set the array index after
 * the last bit index location to -1 to indicate that
 * all bit indexes have been traversed
 *
 * @param   bb  BitBoard to get set bits in
 * @param   arr Integer Array to fill with bit indexes
 填充数组索引的所有部分
  *在给定的64位整数。设置后的数组索引
  *最后一点索引位置1,表示
  *已经遍历所有点索引
  *
  * @param bb位棋盘中位
  * @param arr整数数组填充索引
unsigned long 如何uint64_t
 
 
 */
void getSetBits(uint64_t bb, int * arr){
    int count = 0;
   
    while(bb){
        int lsb = getLSB(bb);//#define getLSB(bb) (LsbLookupTable[(((bb) ^ ((bb)-1)) * 0x03f79d71b4cb0a89ull) >> 58])
        arr[count] = lsb;//                              
        count += 1;
        bb ^= 1ull << lsb;
    }
   
   
    arr[count] = -1;
}


再次感谢二位版主的回复!

2019-09-25 15:23
G笨鸟先飞
Rank: 1
等 级:新手上路
帖 子:4
专家分:0
注 册:2019-9-23
  得分:0 
国际象棋棋盘上有64个交叉点。中国象棋棋盘上有90个交叉点。如果90个数字哈希表与神秘数字找到了,该是什么个样子?
2019-09-25 15:29
G笨鸟先飞
Rank: 1
等 级:新手上路
帖 子:4
专家分:0
注 册:2019-9-23
  得分:0 
https://www.
这个里面讲解的好详细。终于找到了这个…
再次谢谢大家…
以后不懂还会来的…
2019-09-26 09:23
快速回复:求解:90个数字哈希表与神秘数字
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.108801 second(s), 9 queries.
Copyright©2004-2019, BCCN.NET, All Rights Reserved