记得公司面试的第一面时有个面试题.
当时回答出来了.
昨天还是前天的时候偶然间想到那个面试官,又想起来当时的那个题来.
不知道怎么解决了.
囧呀.
上网查了一下,记于此处.
有1G的二进制的文件,为得出其中1的个数,每32位取出一次.设计每次读出32位时,对于该32位数据的处理算法.
即:求32位2进制数据当中1的个数.
分析:
0101 1101 1000 1101 0100 0101 1110 1011
数1的个数
二进制数,每一位上的数字都可以当做该位置上1的个数来看.
那么,这个问题就可以从本质上改写成:
32位2进制数,各位之和.
也就是设计一个计算32位二进制数据,每位之和的算法,
这个问题与之前的问题是等价的,但是给人的思路可是差的远吆.
一个经典的解决方式,针对32位数据,采用相反与分而治之的思路:
1.求相邻两位的和.
2.将相邻的两位作为一个整体,求相邻四位的和.(可以当做,把步骤1得到的结果转化成四进制数,再进行类似步骤1的操作)
3.把相邻的四位作为一个整体,求相邻八位的和.
4.把相邻的八位作为一个整体,求相邻十六位的和.
5.把相邻的十六位作为一个整体,求三十二位的和.
这边有一个流传很广的经典的算法呀.
这个是C的代码呀.
/*
* return number of bits set
*/
#include <stdio.h>
#include <stdlib.h>
unsigned int bitcount32(unsigned int x)
{
x = (x & 0x55555555UL) + ((x >> 1) & 0x55555555UL); // 看一下,5555的二进制,求得相邻两位的和
x = (x & 0x33333333UL) + ((x >> 2) & 0x33333333UL); // 求得相邻四位的和
#if 1
// Version 1 这个好理解一点.再看一下Version 2
x = (x & 0x0f0f0f0fUL) + ((x >> 4) & 0x0f0f0f0fUL); // 求得相邻八位的和
x = (x & 0x00ff00ffUL) + ((x >> 8) & 0x00ff00ffUL); // 求得相邻十六位的和
x = (x & 0x0000ffffUL) + ((x >> 16) & 0x0000ffffUL); //三十二位的和
return x;
#else
// Version 2
x = (x + (x >> 4)) & 0x0f0f0f0fUL; // 0-7 in 4 bits, 八位的1的个数,最多有八个,可以在四位当中存储.
x += x >> 8; // 0-15 in 8 bits 十六位的1的个数,最多有16个,可以在八位当中存储.
x += x >> 16; // 0-31 in 8 bits 32位的1的个数,最多有32个,可以在八位当中存储
return x & 0xff;//取后八位,因为正确的结构保留在后八位.
//可以画一下二进制的图.它比Version 1要简单,但是所作的一半工作在逻辑上是不必要的.从硬件角度来说,又是没任何差别的.
#endif
}
int main()
{
short nVal;
int nCount;
printf("Input a value:");
scanf("%d", &nVal);
nCount = bitcount32(nVal);
printf("BitCount:%d\n", nCount);
system("pause");
return 0;
}
分享到:
相关推荐
标题《苏小妍java面试题.pdf》和描述《JAVA面试题回忆,苏小妍.,2020春招面试的所有题目,仅供后续冲刺者参考。以框架为主,基础知识为辅。》中涉及的是关于Java编程语言面试相关的知识点。具体到文件中提及的几道...
C 语言经典面试题解析 本资源摘要信息涵盖了 2022 年 16 道经典 C 语言面试题,每道题目都包含了详细的解释和分析,以帮助读者更好地理解 C 语言的基本概念和高级应用。 1. 用预处理指令#define 声明一个常数,用...
对于算法问题,除了编写正确的代码外,面试者还需要展示其算法优化的能力,例如如何减少字符串遍历的次数来找到第一个只出现一次的字符。 在编程实践方面,应聘者需要掌握如栈和队列等基本数据结构的操作,以及如何...
2021 北理 北理计算机 889 813 885 考研复试 面试真题回忆 包括听力、口语、综面、人文题和三百多道专业课问答 非常全面,对真题感兴趣的可以下载,更多问题可以关注、私信我
- **继承**:允许一个类(子类)继承另一个类(父类)的属性和方法,从而实现代码复用和扩展。Java只支持单继承,即一个子类只能有一个直接父类,但可以通过接口实现多继承的效果。 2. **代码片段分析**: - ...
Java面试题涵盖了许多核心知识点,包括数据库的参照完整性和性能优化、JavaScript的弹出消息、JSP和Servlet的区别以及Java中的基本类型与包装类的区别,还有并发编程中的锁机制。以下是对这些知识点的详细说明: 1....
轴对称图形是数学中的一个重要概念,尤其在初等几何中占据着核心地位。面试中涉及的初中数学教师资格证真题聚焦于轴对称图形的性质及其教学方法,这对于教师来说,理解和掌握这些知识至关重要。 1. **轴对称图形的...
鼓励学生以《故乡的小路》为主题,创作一个小故事或情景剧,表达对家乡的思念和对过去的回忆。 2. 歌词创作 引导学生尝试修改或创作新的歌词,以自己的家乡为背景,使歌曲更具个性化。 (六)课堂小结 邀请学生分享...
阿里巴巴校园招聘笔试面试题淘宝校园招聘笔试试题27个文档资料合集: 2012阿里巴巴校园招聘阿里云C++笔试试题.doc 2013年阿里巴巴校园招聘笔试试题研发工程师.doc 2014年3月阿里巴巴实习招聘笔试题及部分答案.docx ...
教育岗位面试真题回忆版答案
- **定义**: 在Java中,可以创建一个`volatile`类型的数组,但需要注意的是,这里的`volatile`只适用于数组的引用本身,并不保证数组内的元素在多线程环境下被安全地修改。 - **举例**: 假设我们有一个`volatile int...
Shopee前端面试岗-面试题-历年面经 Shopee前端面试岗-面试题-历年面经 Shopee前端面试岗-面试题-历年面经 Shopee前端面试岗-面试题-历年面经 Shopee 前端岗开发面经汇总 本系列将提供Shopee 前端岗位历年面经,所有...
【标题解析】:“北航 cs 保研面试真题回忆以及经验整理.zip”这个标题表明了文件的内容,主要聚焦于北京航空航天大学(北航)计算机科学(cs)专业的保研面试。保研,即免试推荐研究生,是中国高校中一种选拔优秀...
"2022单片机、MCU、计算机原理笔试面试题" 单片机系统的主要组成模块包括微处理器、存储器、输入/输出接口、时钟电路等。这些模块之间的数据流流向和控制流流向是单片机系统的设计原则的关键。微处理器是单片机系统...
总之,"哈工大cs 保研面试真题回忆以及经验整理.zip"这个压缩包是宝贵的备考资源,通过深入研究和学习,考生可以系统性地提升自己,增加保研成功的可能性。祝愿每位努力的学子都能实现自己的梦想,顺利进入哈工大cs...
这是一个涵盖了国际汉语教学、语言教学、跨文化交际、语法教学、课堂管理等多个方面的面试真题回忆和问题集锦。下面是对这些问题的详细解释和分析: 语言教学 在英语问题1中,学生突然说出“我讨厌你”,作为教师...
回忆版.pdf百度人搜,阿里巴巴,腾讯华为小米搜狗笔试面试八十题.pdf百度校园招聘笔试面试题合集百度校园招聘笔试题web前端2013.pdf百度校园招聘笔试题产品2.pdf百度校园招聘笔试题产品经理2014.pdf百度校园招聘笔试...
"Intel.txt"和"Intel3.txt"以及"Intel面试题.txt"是英特尔公司面试题的进一步扩展,可能包含更多关于优化、性能分析和系统编程的题目,这对于在硬件级别工作或者进行高性能计算的开发者尤为重要。 "威盛笔试题.txt...
Java 面试题详解 Java 是一门流行的编程语言,具有强大的功能和广泛的应用前景。在 Java 面试中,考察者需要具备扎实的 Java 基础知识和面试技巧。本文将对 Java 面试题进行详解,涵盖 final、finally、finalize、...