小编Jun*_*Jun的帖子

在ULK的第5章中,作者声明如下:

"...每个中断处理程序都是相对于自身进行序列化的 - 也就是说,它不能同时执行多个.因此,访问数据结构不需要同步原语"

我不太明白为什么中断处理程序在具有多个内核的现代CPU上"序列化".我想有可能同一个ISR可以同时在不同的内核上运行,对吗？如果是这种情况,如果您不使用自旋锁来保护您的数据,它可能会遇到竞争状态.

所以我的问题是,在一个具有multi-cpus的现代系统中,对于你要编写的每个将要读写一些数据的中断处理程序,是否总是需要自旋锁？

我一直关注基数树的空间使用,但我没有找到任何有用的讨论.

现在假设我们有一个与linux radix-tree.c相同的基数树实现,它接受一个整数并使用每6位来索引树中的下一个位置.我可以很容易地想到基数树的空间使用远远超过二叉搜索树的情况.如果我错了,请纠正我:

使用案例:(0,1,1,1,1),(1,1,1,1,1),(2,1,1,1,1),......(63,1,1,1) ,1).

这里只是为了方便起见,我使用(a,b,c,d,e)来表示一个30位整数键,每个元素代表一个6位值.a是MSB,e是LSB.

基数树:

对于这个用例,基数树的高度为5,每个密钥将占用4个独立的节点,因为它们位于根的不同子树上.所以会有((5-1)*64 + 1)= 257个节点.

每个节点包含2 ^ 6 = 64个指针,因此它将使用257*64*4Byte = 65KB

二叉搜索树

我们只关心有多少钥匙.在这种情况下,它有64个键.

假设每个BST节点每个节点使用3个指针,它将使用64*3*4Byte = 768字节.

对照

看起来基数树空间效率很低.在给定相同数量的节点的情况下,它比二叉搜索树使用~100倍的空间!我不明白为什么它甚至在linux内核中使用.

我错过了什么吗？谢谢.

我正在研究一系列子串问题:

给定一个字符串:

1. 查找仅包含两个具有最大长度的唯一字符的子字符串.
2. 找到包含AT MOST两个唯一字符的所有子串的数量.
3. 查找包含两个唯一字符的所有子字符串的数量.

似乎问题1和2有O(n)解决方案.但是我想不出问题3的O(n)解决方案.(这是问题2的解决方案,这里是问题1).

所以我想知道问题3的O(n)解决方案是否存在？

为问题3添加样本输入/输出:

Given: abbac

Return: 6

因为有6个子串包含两个唯一的字符:ab,abb,abba,bba,ba,ac

当使用C在short和int之间进行转换时,我很困惑.我假设short是16位而int是32位.我测试了下面的代码:

unsigned short a = 0xFFFF;
signed short b = 0xFFFF;

unsigned int u16tou32 = a;
unsigned int s16tou32 = b;
signed int u16tos32 = a;
signed int s16tos32 = b;

printf("%u %u %d %d\n", u16tou32, s16tou32, u16tou32, s16tou32);

我得到的是:

• u16tou32:65535
• s16tou32:4294967295
• u16tos32:65535
• s16tos32:-1

我感到困惑的是s16到u32之间的转换,以及u16到s32之间的转换.似乎s16到u32正在进行"符号扩展",而u16到s32则没有.这背后的规则究竟是什么？这也是依赖于实现的吗？在C中进行这种类型的转换是否安全,或者我应该自己使用位操作来避免意外结果？

我理解为什么C++将INT_MIN定义为(-2147483647-1),但为什么它们不使用1 << 31？这样可以防止溢出并且易于理解.