《编程之美》中不要被阶乘吓倒的一个注解

Lucseeker posted @ 2010年12月17日 03:50 in 未分类 with tags 编程之美 注解 证明 math , 3035 阅读

这一节中的第二个问题:求N!的二进制表示中最低位1的位置。其中第二个解法提出N!含有质因数2的个数等于N减去N的二进制表示中1的数目,不过没有给出证明,自己推导了一下,如下所示。

假设N=anan-1...a1a0,其中ai属于{0, 1},an=1。由于N!中含有质因数2的个数为

[N/2] + [N/4] + [N/8] + [N/16] + ...

=anan-1...a1 + anan-1...a2 + ... + anan-1 + an = S       (1)

以上式子两边同时乘以2,得到

anan-1...a10 + anan-1...a20 + ... + anan-10 + an0 + 0 = 2S      (2)

(2) - (1)错位减,得到:

anan-1...a10 - a1 - a2 - ... - an=S

整理得到

N-(a0 + a1 + a2 + ... + an) = S

注意到ai属于{0, 1},因此就得到证明。

 

JK Board 5th Class M 说:
2022年9月08日 19:18

JKBOSE Model Paper 2023 Class 5 Pdf Download with Answers for English Medium, Hindi Medium, Urdu Medium & Students for Small Answers, Long Answer, Very Long Answer Questions, and Essay Type Questions to Term1 & Term2 Exams at official website. JK Board 5th Class Model Paper New Exam Scheme or Question Pattern for Sammittive Assignment Exams (SA1 & SA2): Very Long Answer (VLA), Long Answer (LA), Small Answer (SA), Very Small Answer (VSA), Single Answer, Multiple Choice and etc.

civaget 说:
2023年12月13日 04:22

Don't overlook the significance of 백링크. They are the lifeblood of SEO. Focus on acquiring links from reputable sources to bolster your website's credibility.

civaget 说:
2023年12月14日 20:19

I always recommend부천출장마사지to friends and family for stress relief.

civaget 说:
2023年12月16日 20:26

Discover the world of 오피 services – a blend of relaxation and entertainment for urbanites.

civaget 说:
2023年12月17日 21:37

I can't believe 누누티비 offers OTT services for free - what a great deal!

civaget 说:
2023年12月18日 00:01

슈어맨's dedication to accuracy sets it apart from the competition.

civaget 说:
2023年12月19日 23:36

Many thanks for bothering to line all of this out for people. This particular posting was in fact very useful in my opinion. 유튜브 프리미엄 무료보기

civaget 说:
2023年12月23日 21:33

Join 해외스포츠중계 for a sports journey that transcends cultures.

civaget 说:
2023年12月23日 21:55

툰코 is the ultimate destination for webtoon enthusiasts, offering a kaleidoscope of stories that stay with you long after you've finished reading.

civaget 说:
2023年12月27日 20:42

안전한 바카라 사이트 is my top choice for baccarat fun and security.

jnanabhumiap.in 说:
2024年1月08日 00:45

JNANABHUMI AP provides all the latest educational updates and many more. The main concept or our aim behind this website has been the will to provide resources with full information on each topic which can be accessed through the Internet. jnanabhumiap.in To ensure that every reader gets what is important and worthy about the topic they search and link to hear from us.

civaget 说:
2024年1月13日 22:34

Youre so cool! I dont suppose Ive read anything like this prior to. So nice to find somebody by incorporating original thoughts on this subject. realy i appreciate you for beginning this up. this site is a thing that is required on the internet, somebody after a little originality. helpful problem for bringing something totally new towards world wide web! 메이저사이트

civaget 说:
2024年1月14日 15:33

I have viewed that smart real estate agents all over the place are getting set to FSBO Marketing. They are noticing that it’s in addition to placing a sign in the front place. It’s really in relation to building associations with these dealers who sooner or later will become consumers. So, once you give your time and effort to helping these traders go it alone — the “Law regarding Reciprocity” kicks in. Thanks for your blog post. คืนยอดเสีย

civaget 说:
2024年1月15日 22:52

Nice post. I was checking continuously this blog and I am impressed! Extremely useful information particularly the last part I care for such info much. I was seeking this particular information for a very long time. Thank you and best of luck. Lahore Sky

seo 说:
2024年1月20日 14:32

From all the blogs Ive understand lately, this one appears to be essentially the most moving C it gave me something to bear in mind. EndoBoost

seo 说:
2024年1月20日 15:31

Cause of Arthritis… [...]just below, are some totally unrelated sites to ours, however, they are definitely worth checking out[...]… search classified ads

seo 说:
2024年1月20日 19:20

When I initially commented I clicked the -Notify me when new comments are added- checkbox and now each time a remark is added I get four emails with the same comment. Is there any manner you possibly can take away me from that service? Thanks! accountant in SA

seo 说:
2024年1月21日 14:35

An interesting discussion is worth comment. I do think that you should write read more about this topic, it will not be considered a taboo subject but usually everyone is too few to communicate in on such topics. To another. Cheers The Billionaire Brain Wave

seo 说:
2024年1月21日 18:25

Thank you, I’ve recently been looking for info about this subject for ages and yours is the greatest I’ve found out so far. But, what in regards to the bottom line? Are you sure concerning the supply? auditor

jnanabhumiap.in 说:
2024年1月22日 16:44

JNANABHUMI AP provides a CBSE syllabus for all classes for the academic year 2024 has been designed as per the guidelines of the CBSE Board. The syllabus offers a conceptual background and lays the groundwork for the Class 10 Board exams. jnanabhumiap.in By visiting the page, students will find the downloadable pdf of the reduced CBSE 10th Syllabus along with the deleted portion of the syllabus for each subject. So, students are advised to prepare for the exam, as per the syllabus mentioned here.

seo 说:
2024年1月23日 13:16

I would like to thnkx for the efforts you have put in writing this website. I am hoping the same high-grade blog post from you in the upcoming also. Actually your creative writing skills has encouraged me to get my own site now. Really the blogging is spreading its wings fast. Your write up is a good example of it. The Growth Matrix

seo 说:
2024年1月23日 17:04

I impressed, I must say. Really rarely do I encounter a blog that both educative and entertaining, and let me inform you, you’ve got hit the nail on the head. Your thought is outstanding; the issue is something that not sufficient people are speaking intelligently about. I’m very pleased that I stumbled throughout this in my seek for one thing regarding this. Shape Capsules

seo 说:
2024年1月24日 15:37

Hi there, I must say that Tales from abroad » Blog Archive » Rafting is a extremely excellent place to slack from function I really really like your blog and I’ve already bookmarked it. Make sure you, maintain it up to date much more often. Thank you! Jungle Beast Pro Reviews

seo 说:
2024年1月24日 17:38

On this very topic, I try update my blogs almost like I’m speaking to somebody or talking to that reader directly as I consider it helps engage people a lot more than writing content formally especially when my own blog is based around the goings ons, daily thoughts and research about this somewhat controversial concern. I discovered that I nonetheless need to use more of the methods you have mentioned in this posting. RYAN MCLANE

jnanabhumiap.in 说:
2024年1月24日 22:10

JNANABHUMI AP provides a CBSE syllabus for all classes for the academic year 2024 has been designed as per the guidelines of the CBSE Board. The syllabus offers a conceptual background and lays the groundwork for the Class 10 Board exams. jnanabhumiap.in By visiting the page, students will find the downloadable pdf of the reduced CBSE 10th Syllabus along with the deleted portion of the syllabus for each subject. So, students are advised to prepare for the exam, as per the syllabus mentioned here.

seo 说:
2024年1月25日 15:16

I took a break to view your article. I found it very relaxing Herpagreens Reviews

seo 说:
2024年1月30日 16:24

Youre so cool! I dont suppose Ive learn something like this before. So good to search out any person with some unique thoughts on this subject. realy thanks for starting this up. this website is one thing that’s wanted on the net, somebody with a bit originality. helpful job for bringing one thing new to the internet! Herpagreens Reviews

seo 说:
2024年1月31日 17:22

I wouldn’t normally be so intrigued by content on this topic but the way you wrote this really grabbed my attention. It is very well thought out and interesting informative content. Thank you for sharing! The Growth Matrix reviews


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter