大整数乘法

很长时间都没写过代码了,试着写了这个常见的题目。整体思路:采用整形链表记录大整数的每一位,然后分别遍历乘数和被乘数的每一位,将每两个数字的乘积累加到结果的相应位上面。针对大整数类型,重载输入和输出流,重载乘法。

输出部分实现不是特别好。用STL的容器实现链表也许会简单的多。重载乘法的实现不合常理,本应该返回一个新的对象,为了简单起见,直接返回了新对象的指针;在计算乘法结果时使用了一个递归,理论上来说有可能深度过大,导致栈溢出;另外对于指针和应用的使用不规范。

具体代码:

阅读全文 »

| 1 分2 分3 分4 分5 分 (4.83- 6票) Loading ... Loading ... | 归档目录:C/C++, 算法数据结构 |

全部日志列表

  1. [ 三月 23, 2021 ]
  2. [ 三月 8, 2021 ]
  3. [ 三月 7, 2021 ]
  4. [ 一月 17, 2021 ]
  5. [ 一月 1, 2021 ]
  6. [ 十二月 31, 2020 ]
  7. [ 十二月 20, 2020 ]
  8. [ 十二月 13, 2020 ]
  9. [ 十二月 9, 2020 ]
  10. [ 十二月 5, 2020 ]
  11. [ 十一月 21, 2020 ]
  12. [ 十一月 21, 2020 ]
  13. [ 十月 21, 2020 ]
  14. [ 十月 7, 2020 ]
  15. [ 九月 25, 2020 ]
  16. [ 八月 16, 2020 ]
  17. [ 八月 15, 2020 ]
  18. [ 八月 6, 2020 ]
  19. [ 八月 2, 2020 ]
  20. [ 八月 2, 2020 ]
  21. [ 七月 21, 2020 ]
  22. [ 七月 4, 2020 ]
  23. [ 九月 14, 2019 ]
  24. [ 八月 4, 2018 ]
  25. [ 七月 7, 2018 ]
  26. [ 六月 15, 2018 ]
  27. [ 五月 27, 2018 ]
  28. [ 三月 17, 2018 ]
  29. [ 二月 11, 2018 ]
  30. [ 一月 24, 2018 ]
  31. [ 一月 6, 2018 ]
  32. [ 十二月 30, 2017 ]
  33. [ 十二月 28, 2017 ]
  34. [ 十二月 28, 2017 ]
  35. [ 十月 22, 2017 ]
  36. [ 十月 22, 2017 ]
  37. [ 十月 8, 2017 ]
  38. [ 十月 8, 2017 ]
  39. [ 九月 1, 2017 ]
  40. [ 七月 29, 2017 ]
  41. [ 六月 25, 2017 ]
  42. [ 十二月 5, 2016 ]
  43. [ 十月 15, 2016 ]
  44. [ 九月 25, 2016 ]
  45. [ 七月 23, 2016 ]
  46. [ 七月 10, 2016 ]
  47. [ 六月 19, 2016 ]
  48. [ 二月 28, 2016 ]
  49. [ 二月 13, 2016 ]
  50. [ 二月 12, 2016 ]
  51. [ 十二月 16, 2015 ]
  52. [ 十二月 10, 2015 ]
  53. [ 十二月 10, 2015 ]
  54. [ 十一月 25, 2015 ]
  55. [ 十一月 1, 2015 ]
  56. [ 十月 7, 2015 ]
  57. [ 八月 22, 2015 ]
  58. [ 八月 22, 2015 ]
  59. [ 七月 19, 2015 ]
  60. [ 七月 14, 2015 ]
  61. [ 七月 14, 2015 ]
  62. [ 七月 5, 2015 ]
  63. [ 六月 3, 2015 ]
  64. [ 三月 14, 2015 ]
  65. [ 三月 13, 2015 ]
  66. [ 二月 4, 2015 ]
  67. [ 一月 18, 2015 ]
  68. [ 一月 15, 2015 ]
  69. [ 一月 15, 2015 ]
  70. [ 一月 7, 2015 ]
  71. [ 十二月 31, 2014 ]
  72. [ 十二月 21, 2014 ]
  73. [ 十一月 21, 2014 ]
  74. [ 十一月 16, 2014 ]
  75. [ 十月 18, 2014 ]
  76. [ 十月 16, 2014 ]
  77. [ 十月 15, 2014 ]
  78. [ 十月 15, 2014 ]
  79. [ 十月 15, 2014 ]
  80. [ 九月 26, 2014 ]
  81. [ 九月 24, 2014 ]
  82. [ 九月 16, 2014 ]
  83. [ 九月 13, 2014 ]
  84. [ 九月 7, 2014 ]
  85. [ 九月 7, 2014 ]
  86. [ 九月 6, 2014 ]
  87. [ 九月 3, 2014 ]
  88. [ 八月 28, 2014 ]
  89. [ 八月 25, 2014 ]
  90. [ 八月 24, 2014 ]
  91. [ 八月 21, 2014 ]
  92. [ 八月 17, 2014 ]
  93. [ 八月 14, 2014 ]
  94. [ 八月 9, 2014 ]
  95. [ 八月 7, 2014 ]
  96. [ 八月 7, 2014 ]
  97. [ 八月 7, 2014 ]
  98. [ 八月 7, 2014 ]
  99. [ 七月 31, 2014 ]
  100. [ 七月 27, 2014 ]
  101. [ 七月 27, 2014 ]
  102. [ 七月 27, 2014 ]
  103. [ 七月 24, 2014 ]
  104. [ 七月 20, 2014 ]
  105. [ 七月 20, 2014 ]
  106. [ 七月 20, 2014 ]
  107. [ 七月 19, 2014 ]
  108. [ 七月 15, 2014 ]
  109. [ 七月 14, 2014 ]
  110. [ 七月 12, 2014 ]
  111. [ 七月 10, 2014 ]
  112. [ 七月 10, 2014 ]
  113. [ 七月 7, 2014 ]
  114. [ 七月 5, 2014 ]
  115. [ 七月 5, 2014 ]
  116. [ 六月 27, 2014 ]
  117. [ 六月 25, 2014 ]
  118. [ 六月 20, 2014 ]
  119. [ 六月 12, 2014 ]
  120. [ 六月 8, 2014 ]
  121. [ 六月 7, 2014 ]
  122. [ 六月 2, 2014 ]
  123. [ 五月 29, 2014 ]
  124. [ 五月 25, 2014 ]
  125. [ 五月 24, 2014 ]
  126. [ 五月 22, 2014 ]
  127. [ 五月 17, 2014 ]
  128. [ 五月 16, 2014 ]
  129. [ 五月 15, 2014 ]
  130. [ 五月 15, 2014 ]
  131. [ 五月 14, 2014 ]
  132. [ 五月 11, 2014 ]
  133. [ 五月 7, 2014 ]
  134. [ 五月 7, 2014 ]
  135. [ 五月 5, 2014 ]
  136. [ 五月 4, 2014 ]
  137. [ 五月 4, 2014 ]
  138. [ 四月 30, 2014 ]
  139. [ 四月 27, 2014 ]
  140. [ 四月 25, 2014 ]
  141. [ 四月 23, 2014 ]
  142. [ 四月 19, 2014 ]
  143. [ 四月 17, 2014 ]
  144. [ 四月 15, 2014 ]
  145. [ 四月 13, 2014 ]
  146. [ 四月 13, 2014 ]
  147. [ 四月 13, 2014 ]
  148. [ 四月 11, 2014 ]
  149. [ 四月 11, 2014 ]
  150. [ 四月 11, 2014 ]
  151. [ 四月 8, 2014 ]
  152. [ 四月 3, 2014 ]
  153. [ 四月 1, 2014 ]
  154. [ 三月 28, 2014 ]
  155. [ 三月 27, 2014 ]
  156. [ 三月 27, 2014 ]
  157. [ 三月 26, 2014 ]
  158. [ 三月 26, 2014 ]
  159. [ 三月 26, 2014 ]
  160. [ 三月 25, 2014 ]
  161. [ 三月 22, 2014 ]
  162. [ 三月 22, 2014 ]
  163. [ 三月 19, 2014 ]
  164. [ 三月 11, 2014 ]
  165. [ 三月 9, 2014 ]
  166. [ 三月 7, 2014 ]
  167. [ 三月 5, 2014 ]
  168. [ 二月 20, 2014 ]
  169. [ 二月 18, 2014 ]
  170. [ 二月 12, 2014 ]
  171. [ 二月 9, 2014 ]
  172. [ 二月 7, 2014 ]
  173. [ 十二月 29, 2013 ]
  174. [ 十二月 26, 2013 ]
  175. [ 十二月 26, 2013 ]
  176. [ 十二月 8, 2013 ]
  177. [ 十二月 3, 2013 ]
  178. [ 十一月 16, 2013 ]
  179. [ 十一月 16, 2013 ]
  180. [ 十一月 3, 2013 ]
  181. [ 十月 27, 2013 ]
  182. [ 十月 27, 2013 ]
  183. [ 十月 27, 2013 ]
  184. [ 十月 24, 2013 ]
  185. [ 十月 20, 2013 ]
  186. [ 十月 16, 2013 ]
  187. [ 十月 15, 2013 ]
  188. [ 十月 14, 2013 ]
  189. [ 十月 12, 2013 ]
  190. [ 十月 11, 2013 ]
  191. [ 十月 4, 2013 ]
  192. [ 十月 2, 2013 ]
  193. [ 十月 2, 2013 ]
  194. [ 九月 29, 2013 ]
  195. [ 九月 27, 2013 ]
  196. [ 九月 20, 2013 ]
  197. [ 九月 19, 2013 ]
  198. [ 九月 14, 2013 ]
  199. [ 九月 10, 2013 ]
  200. [ 九月 9, 2013 ]
  201. [ 九月 9, 2013 ]
  202. [ 九月 6, 2013 ]
  203. [ 九月 4, 2013 ]
  204. [ 九月 4, 2013 ]
  205. [ 九月 3, 2013 ]
  206. [ 九月 3, 2013 ]
  207. [ 八月 26, 2013 ]
  208. [ 八月 24, 2013 ]
  209. [ 八月 24, 2013 ]
  210. [ 八月 24, 2013 ]
  211. [ 八月 18, 2013 ]
  212. [ 八月 18, 2013 ]
  213. [ 八月 17, 2013 ]
  214. [ 八月 11, 2013 ]
  215. [ 八月 10, 2013 ]
  216. [ 八月 10, 2013 ]
  217. [ 八月 5, 2013 ]
  218. [ 八月 3, 2013 ]
  219. [ 八月 3, 2013 ]
  220. [ 七月 31, 2013 ]
  221. [ 七月 30, 2013 ]
  222. [ 七月 28, 2013 ]
  223. [ 七月 21, 2013 ]
  224. [ 七月 14, 2013 ]
  225. [ 七月 14, 2013 ]
  226. [ 七月 13, 2013 ]
  227. [ 七月 6, 2013 ]
  228. [ 七月 3, 2013 ]
  229. [ 六月 25, 2013 ]
  230. [ 六月 25, 2013 ]
  231. [ 六月 25, 2013 ]
  232. [ 六月 25, 2013 ]
  233. [ 六月 19, 2013 ]
  234. [ 六月 16, 2013 ]
  235. [ 六月 6, 2013 ]
  236. [ 六月 1, 2013 ]
  237. [ 五月 11, 2013 ]
  238. [ 三月 8, 2013 ]
  239. [ 三月 5, 2013 ]
  240. [ 三月 1, 2013 ]
  241. [ 一月 3, 2013 ]
  242. [ 九月 15, 2012 ]
  243. [ 九月 14, 2012 ]
  244. [ 九月 14, 2012 ]
  245. [ 九月 13, 2012 ]
  246. [ 九月 13, 2012 ]
  247. [ 九月 12, 2012 ]
  248. [ 九月 9, 2012 ]
  249. [ 九月 8, 2012 ]
  250. [ 九月 8, 2012 ]
  251. [ 九月 7, 2012 ]
  252. [ 九月 2, 2012 ]
  253. [ 九月 1, 2012 ]
  254. [ 八月 31, 2012 ]
  255. [ 八月 31, 2012 ]
  256. [ 八月 31, 2012 ]
  257. [ 二月 13, 2011 ]
  258. [ 三月 28, 2009 ]
  259. [ 二月 14, 2009 ]
  260. [ 十一月 5, 2008 ]
  261. [ 六月 7, 2008 ]
  262. [ 四月 28, 2008 ]
  263. [ 三月 13, 2008 ]
| 1 分2 分3 分4 分5 分 (5.00- 21票) Loading ... Loading ... | 归档目录:建站技术 |

基于netlink的内核态与用户态异步并发消息处理模型

用户态采用select模型,初始化时建立多个netlinksocket,绑定完成之后,向内核发送握手消息,这样内核可以将已经建立的连接记住,以便后续选择可用的连接发送数据。初始化和握手完成之后,由内核主动向用户态发送数据,用户态主线程在各个socket句柄上面等待读事件的到来,当检测到读事件时,向线程池提交数据读取和处理任务。这样模拟一个连接池和事件分发模型,保证内核数据及时被读取到用户态程序并处理,能做到并发。

而内核态的netlink在接收数据时本身就是以系统调用的方式提供给业务层的发送接口,因此本身就是异步的,性能不是问题。内核态收到数据时,只需要提交给一个内核线程去处理即可。

原型代码如下:

阅读全文 »

| 1 分2 分3 分4 分5 分 (5.00- 8票) Loading ... Loading ... | 归档目录:C/C++, Linux内核 |

监控dmesg实时输出

#!/bin/bash
end=`dmesg |wc -l`
while true
do
sleep 1
end2=`dmesg |wc -l`

if [ "$end" != "$end2" ]; then
dmesg |awk '{print NR, $0}'|tail -$((end2-end))
end=$end2
fi

if [ "$end" -ge 1000 ]
then
dmesg -c >/dev/null 2>&1
echo "**********************"
echo "*dmesg -c now; *"
echo "**********************"
end=`dmesg |wc -l`
fi

done

| 1 分2 分3 分4 分5 分 (5.00- 4票) Loading ... Loading ... | 归档目录:实用脚本 |

关于fork和行缓冲的问题

一段关于fork函数调用的代码,问最终屏幕上会打印出多少个“-”。
#include<unistd.h>
#include<stdio.h>

int main()
{
for(int i = 0; i < 2; ++i)
{
fork();
printf("-");
}

printf("\n");
return 0;
}

阅读全文 »

| 1 分2 分3 分4 分5 分 (5.00- 5票) Loading ... Loading ... | 归档目录:C/C++, 职业发展, 软件技术 | 标签: |

试写atoi函数

int atoi(const char* strNum);

思路:首先对输入指针判空,然后取出每一位的权值a,用类似下面的算法:Math.pow(10, i) * a 这样的算法实现。用到了乘方算法,似乎不是特别好。另外用一个类似递归的思想:sum = sum * 10 + digitnum; ,下面就后者给出实现代码。

在接口中用到了const char*,想了半天,到底是指针是const还是指向const char的指针呢,在The C++ Programming Language里面给出过一个助记的方法:把一个声明从右向左读。因此const char*是指后者。
 
atoi函数库文件编写:

阅读全文 »

| 1 分2 分3 分4 分5 分 (4.71- 7票) Loading ... Loading ... | 归档目录:C/C++, 算法数据结构 |

Jetty误判长连接为超时连接的问题

在上一篇中介绍了jetty的反映器模型,selector线程与业务子线程交互的点有:

1、分发事件给子线程做,启动子线程;

2、子线程发现阻塞或者连接关闭等时间时,注册内部changes,等待selector线程调度;

3、检测超时连接,并且关闭连接。

阅读全文 »

| 1 分2 分3 分4 分5 分 (5.00- 8票) Loading ... Loading ... | 归档目录:Jetty | 标签: |

Jetty线程“互锁”导致数据传输性能降低问题分析

以下分析针对jetty的特定版本:http://dev.eclipse.org/svnroot/rt/org.eclipse.jetty/jetty/tags/jetty-7.2.1.v20101111

首先介绍一下Jetty的反映器模型,Jetty用的经典的NIO异步模型(Scalable IO in Java http://gee.cs.oswego.edu/dl/cpjslides/nio.pdf)。连接管理的示意图如下:

pool

Jetty在使用这个模型的时候,做了一些改动,acceptor是独立出来的一个阻塞线程,用于阻塞地接受新的连接请求,而所有的连接建立之后,都会想selector线程注册网络事件和内部的事件(changes),selector需要同时处理网络事件和内部的changes。同时还要定期检查超时的链接。

阅读全文 »

| 1 分2 分3 分4 分5 分 (5.00- 16票) Loading ... Loading ... | 归档目录:Jetty | 标签: |

《求a & x 的取值集合》解答改进版

按照上一篇中提到的思路,最后问题的焦点在于:怎样快速找到tmp中的为1的bit位在x中的实际位置。这样在计算N值的同时将每一位的权值与索引位置的关系用数组对照起来,最后只需要在遍历tmp的值为1的bit位时作相应的加权累加即可。
也综合评论中提到的递归方案,重新补充了各个方案的代码和性能测试代码。

见“方案1”的代码处:

阅读全文 »

| 1 分2 分3 分4 分5 分 (4.40- 5票) Loading ... Loading ... | 归档目录:C/C++, Java, 算法数据结构, 职业发展 |

给定一个long型常量,其值为x,给定long型变量a,要求a & x 的取值集合

给定一个long型常量,其值为x,给定long型变量a,要求a & x 的取值集合,结果放入ArrayList中。

思路,x先转换为bit数组,得出其中元素值为1的总数为n,则所有取值的总数为2的n次方,记为N。
在0~N的闭区间中,依次取出各个数值,记为tmp,将tmp也转换为bit数组,依次遍历x的每一个bit位,当x的bit位为1时,到tmp中去取出相应的bit位,如果也为1,则将该位为1时,其他所有位为0时所代表的数值累加到结果中。
遍历完所有的bit位后,得到的结果即为所需要的数值。

整个思路有点复杂,性能也不高,从数值本身的与或运算上面着手,肯定还有更简单的方法。

代码:

阅读全文 »

| 1 分2 分3 分4 分5 分 (4.75- 4票) Loading ... Loading ... | 归档目录:Java, 算法数据结构, 职业发展 |
返回顶部